Other Mathematics Commons^™

A Complete Characterization Of Near Outer-Planar Graphs, Tanya Allen Lueder Genannt Luehr

Doctoral Dissertations

A graph is outer-planar (OP) if it has a plane embedding in which all of the vertices lie on the boundary of the outer face. A graph is near outer-planar (NOP) if it is edgeless or has an edge whose deletion results in an outer-planar graph. An edge of a non outer-planar graph whose removal results in an outer-planar graph is a vulnerable edge. This dissertation focuses on near outer-planar (NOP) graphs. We describe the class of all such graphs in terms of a finite list of excluded graphs, in a manner similar to the well-known Kuratowski Theorem for planar …