On graph planarity and semi-duality (Q5931417)

This paper describes some recent results on graph planarity. Some of the results cited have appeared elsewhere, some are newly presented. A graph is quasi-4-connected if it is 3-connected and the only 3-cuts have two components, one of which is a single vertex. NEWLINENEWLINENEWLINEThe first set of results are generalizations of Kuratowski's theorem giving an excluded subgraph characterization of planar graphs. These usually consist of finding Kuratowski subgraphs \(K_5\) or \(K_{3,3}\) with special structures, for example that some of the edges of the Kuratowski subgraph are also edges in the original graph. Some special cases examined are when the graph is quasi-4-connected, cubic, triangle-free, or bipartite. NEWLINENEWLINENEWLINEThe second set of results are related to Whitney's theorem: loosely speaking, that a graph is planar if and only if it has a dual. These are phrased in terms of matriods. A natural definition is given that generalizes matroid duality for graphs. Several generalizations of Whitney's theorem are given.