Mac Lane's planarity criterion (original) (raw)
In graph theory, Mac Lane's planarity criterion is a characterisation of planar graphs in terms of their cycle spaces, named after Saunders Mac Lane, who published it in 1937. It states that a finite undirected graph is planar if and only if the cycle space of the graph (taken modulo 2) has a cycle basis in which each edge of the graph participates in at most two basis vectors.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, Mac Lane's planarity criterion is a characterisation of planar graphs in terms of their cycle spaces, named after Saunders Mac Lane, who published it in 1937. It states that a finite undirected graph is planar if and only if the cycle space of the graph (taken modulo 2) has a cycle basis in which each edge of the graph participates in at most two basis vectors. (en) En théorie des graphes, le critère de planarité de Mac Lane est une caractérisation des graphes planaires par leur (en), nommée d'après Saunders Mac Lane qui l'a publiée en 1937. Le critère dit qu'un graphe est planaire si et seulement si son espace de cycles (pris modulo 2) possède une (en) dans laquelle chaque arête du graphe contribue à au plus deux vecteurs de la base. (fr) Критерий планарности Маклейна — это описание планарных графов в терминах их пространства циклов. Критерий носит имя Саундерса Маклейна, опубликовавшего критерий в 1937. Критерий утверждает, что конечный неориентированный граф является планарным тогда и только тогда, когда пространство циклов графа (по модулю 2) имеет базис циклов, в котором каждое ребро графа принадлежит не более чем двум базисным векторам. (ru) Крите́рій плана́рності Макле́йна — це опис планарних графів у термінах їхнього простору циклів. Критерій носить ім'я , який опублікував його 1937 року. Критерій стверджує, що скінченний неорієнтований граф є планарним тоді й лише тоді, коли простір циклів графа (за модулем 2) має базис циклів, у якому кожне ребро графа належить не більше ніж двом базисним векторам. (uk) |
| dbo:wikiPageExternalLink | http://matwbn.icm.edu.pl/ksiazki/fm/fm28/fm2814.pdf |
| dbo:wikiPageID | 781806 (xsd:integer) |
| dbo:wikiPageLength | 9422 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1094648555 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Saunders_Mac_Lane dbr:Meshedness_coefficient dbr:Algebraic_topology dbr:Cycle_basis dbr:Cycle_space dbr:Undirected_graph dbc:Planar_graphs dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Graph_minor dbr:SIAM_Journal_on_Computing dbr:Parallel_algorithm dbr:Spanning_tree dbr:Peripheral_cycle dbc:Algebraic_graph_theory dbr:Linear_independence dbr:Finite_field dbr:Graph_theory dbr:Planar_graph dbr:Circuit_rank dbr:SPQR_tree dbr:Euler_characteristic dbr:Wagner's_theorem dbr:Forbidden_minor |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harv dbt:Harvtxt dbt:Math dbt:Mvar dbt:Short_description |
| dct:subject | dbc:Planar_graphs dbc:Algebraic_graph_theory |
| gold:hypernym | dbr:Characterisation |
| rdf:type | yago:Abstraction100002137 yago:Communication100033020 yago:Graph107000195 yago:VisualCommunication106873252 yago:WikicatPlanarGraphs |
| rdfs:comment | In graph theory, Mac Lane's planarity criterion is a characterisation of planar graphs in terms of their cycle spaces, named after Saunders Mac Lane, who published it in 1937. It states that a finite undirected graph is planar if and only if the cycle space of the graph (taken modulo 2) has a cycle basis in which each edge of the graph participates in at most two basis vectors. (en) En théorie des graphes, le critère de planarité de Mac Lane est une caractérisation des graphes planaires par leur (en), nommée d'après Saunders Mac Lane qui l'a publiée en 1937. Le critère dit qu'un graphe est planaire si et seulement si son espace de cycles (pris modulo 2) possède une (en) dans laquelle chaque arête du graphe contribue à au plus deux vecteurs de la base. (fr) Критерий планарности Маклейна — это описание планарных графов в терминах их пространства циклов. Критерий носит имя Саундерса Маклейна, опубликовавшего критерий в 1937. Критерий утверждает, что конечный неориентированный граф является планарным тогда и только тогда, когда пространство циклов графа (по модулю 2) имеет базис циклов, в котором каждое ребро графа принадлежит не более чем двум базисным векторам. (ru) Крите́рій плана́рності Макле́йна — це опис планарних графів у термінах їхнього простору циклів. Критерій носить ім'я , який опублікував його 1937 року. Критерій стверджує, що скінченний неорієнтований граф є планарним тоді й лише тоді, коли простір циклів графа (за модулем 2) має базис циклів, у якому кожне ребро графа належить не більше ніж двом базисним векторам. (uk) |
| rdfs:label | Critère de planarité de Mac Lane (fr) Mac Lane's planarity criterion (en) Критерий планарности Маклейна (ru) Критерій планарності Маклейна (uk) |
| owl:sameAs | freebase:Mac Lane's planarity criterion yago-res:Mac Lane's planarity criterion wikidata:Mac Lane's planarity criterion dbpedia-fr:Mac Lane's planarity criterion dbpedia-ru:Mac Lane's planarity criterion dbpedia-uk:Mac Lane's planarity criterion https://global.dbpedia.org/id/4qr3z |
| prov:wasDerivedFrom | wikipedia-en:Mac_Lane's_planarity_criterion?oldid=1094648555&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Mac_Lane's_planarity_criterion |
| is dbo:knownFor of | dbr:Saunders_Mac_Lane |
| is dbo:wikiPageRedirects of | dbr:MacLane's_planarity_criterion dbr:MacLane_planarity_criterion dbr:Mac_Lane_planarity_criterion |
| is dbo:wikiPageWikiLink of | dbr:Saunders_Mac_Lane dbr:List_of_graph_theory_topics dbr:Cycle_basis dbr:Cycle_space dbr:Planar_graph dbr:Planarity_testing dbr:MacLane's_planarity_criterion dbr:MacLane_planarity_criterion dbr:Mac_Lane_planarity_criterion |
| is dbp:knownFor of | dbr:Saunders_Mac_Lane |
| is foaf:primaryTopic of | wikipedia-en:Mac_Lane's_planarity_criterion |