Outerplanar Partitions of Planar Graphs

Anouterplanargraph is one that can be embedded in the plane so that all of the vertices lie on one of the faces. We investigate a conjecture of Chartrand, Geller, and Hedetniemi, that every planar graph can be edge-partitioned into two outerplanar subgraphs. We refute the stronger statement that every planarly embedded graph can be edge-partitioned into two outerplanar subgraphs, one of which is outerplanarly embedded. We give a method that yields outerplanar partitions of certain graphs not covered by previous results. We formulate a conjecture about 4-connected maximal planar graphs that implies the original conjecture. Finally, we verify a weaker form of the conjecture in which outerplanar subgraphs are replaced by subgraphs with no homeomorphs ofK4.