Authors: Došen, Kosta 
Petrić, Zoran 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: A planarity criterion for graphs
Journal: SIAM Journal on Discrete Mathematics
Volume: 29
Issue: 4
First page: 2160
Last page: 2165
Issue Date: 1-Jan-2015
Rank: M22
ISSN: 0895-4801
DOI: 10.1137/140954957
It is proved 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 K33 and K5, but the criterion itself does not mention K3,3 and K5. Some other variants of the criterion are also shown necessary and sufficient for planarity.
Keywords: Cocycle | Kuratowski's graphs | Planar graph
Publisher: Society for Industrial and Applied Mathematics Publications

Show full item record


checked on Jul 19, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.