A planarity criterion for graphs

DOI10.1137/140954957zbMATH Open1327.05074arXiv1203.0996OpenAlexW2132897805MaRDI QIDQ3452159FDOQ3452159

Authors: Kosta Došen, Zoran Petrić 

Publication date: 18 November 2015

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

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.

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

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)

zbMATH Keywords

cocycleplanar graphKuratowski's graphs

Mathematics Subject Classification ID

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

Cites Work

• Another characterisation of planar graphs
• Title not available (Why is that?)
• Kuratowski's theorem
• Title not available (Why is that?)
• The Jordan Curve Theorem Via the Brouwer Fixed Point Theorem
• Title not available (Why is that?)

Cited In (6)

• A structural property of planar graphs
• A criterion for the planarity of a graph
• MacLane's planarity criterion for locally finite graphs
• A Characterization of Graphic Matroids Based on Circuit Orderings
• A strengthening of the Kuratowski planarity criterion for 3-connected graphs
• The theorem on planar 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)