An outerplanar graph 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 of K-4. (C) 1996 Academic Press, Inc. [References: 7]
展开▼
