Interior Graphs of Maximal Outerplane Graphs
Maciej Syslo, Andrzej Proskurowski, Sandra Hedetniemi
Committee:
Technical Report(May 1983)
Keywords:

A maximal outerplane graph (mop) is a plane embedding of a graph in which all vertices lie on the exterior face, and the addition of an edge between any two vertices would destroy this outerplanarity property. Removing the edges of the exterior face of a mop G results in the interior graph of G. We give a necessary and sufficient condition for a graph to be the interior graph of some mop.