Abstract: Kuratowski's Theorem, perhaps the most famous result in graph theory, states that K 5 and K 3,3 are the only non-planar graphs for which both G \ e , the deletion of the edge e, and G / e , the contraction of the edge e , are planar for all edges e of G . We characterize the almost-planar graphs, those non-planar graphs for which G \ e or G / e is planar for all edges e of G . This paper gives two characterizations of the almost-planar graphs: an explicit description of the structure of almost-planar graphs; and an excluded minor criterion. We also give a best possible bound on the number of edges of an almost-planar graph.
Publication Year: 1996
Publication Date: 1996-09-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 15
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot