A planarity criterion for graphs

DOI10.1137/140954957MaRDI QIDQ3452159zbMATHOpenAlexFDO

Authors Kosta Došen, Zoran Petrić

Publication date 18 November 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.0996

zbMATH Keywords

cocycleplanar graphKuratowski's graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: It is proven that a connected graph is planar if and only if all its cocycles with at least four edges are "grounded" in the graph. The notion of grounding of this planarity criterion, which is purely combinatorial, stems from the intuitive idea that with planarity there should be a linear ordering of the edges of a cocycle such that in the two subgraphs remaining after the removal of these edges there can be no crossing of disjoint paths that join the vertices of these edges. The proof given in the paper of the right-to-left direction of the equivalence is based on Kuratowski's Theorem for planarity involving K_{3,3} and K_5, but the criterion itself does not mention K_{3,3} and K_5. Some other variants of the criterion are also shown necessary and sufficient for planarity.

Recommendations

• A criterion for the planarity of a graph
• A strengthening of the Kuratowski planarity criterion for 3-connected graphs
• MacLane's planarity criterion for locally finite graphs
• scientific article; zbMATH DE number 475620
• Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)

Cites work

• scientific article; zbMATH DE number 1033818 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• Another characterisation of planar graphs
• Kuratowski's theorem
• The Jordan Curve Theorem Via the Brouwer Fixed Point Theorem

Cited in

(6)

• A structural property of planar graphs
• A characterization of graphic matroids based on circuit orderings
• The theorem on planar graphs
• MacLane's planarity criterion for locally finite graphs
• A criterion for the planarity of a graph
• A strengthening of the Kuratowski planarity criterion for 3-connected graphs

This page was built for publication: A planarity criterion for graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452159)