A graph is outerplanar if it can be embedded in the plane so that every vertex lies on the unbounded outside face. Chartrand, Geller, and Hedetniemi [CGH] conjectured the following.

Conjecture: Every planar graph can be edge-partitioned into two outerplanar graphs.

Observe that the conjecture is true for Hamiltonian graphs; the desired partition is the inside versus the outside of the Hamiltonian cycle (the cycle can be included in either or both parts). In particular, the conjecture is true for 4-connected planar graphs as they are Hamiltonian by a result of Tutte [T]. However, not every planar graph is a subgraph of a Hamiltonian planar graph.

Nash-Williams [N] gives a necessary and sufficient condition for a graph to have an edge-partition into a given number of forests. His result implies that every planar graph is the union of three forests. Hence such a graph is the union of three outerplanar graphs. His results also show that every outerplanar graph is the union of two forests, but it is unclear if this helps solve the above conjecture.

Note that it suffices to prove the conjecture for triangulations.

The best known partial result is due to Kedlaya [K]. He shows that every planar graph can be edge-partitioned into to two graphs neither of which contain a homeomorph of K_4 (outerplanar graphs are characterized by excluding subdivisions of K_4 and K_{2,3}). However, he refutes the stronger conjecture that every planar graph edge-partitions into a forest and an outerplanar graph, or into two outerplanar graphs with the same outer boundary cycle. Even better, Elmallah and Colbourn [EC] have shown that there exist planar graphs which cannot be edge partitioned into a forest and a series-parallel graph.

 I believe that the conjecture has been claimed to be true several times, but the proofs did not bear scrutiny.

 References:

[CGH] G. Chartrand, D.P. Geller, and S. Hedetniemi, Graphs with forbidden subgraphs, J. Combin. Theory B 10 (1971) 12-41.

[EC] E. Elmallah and C. Colbourn, Partitioning the edges of a planar graph into two partial k-trees, Congressus Numerantium 66 (1988) 69-80.

[K] K. Kedlaya, Outerplanar partitions of planar graphs, J. of Combin. Th. Ser. B 67 (1996) 238-248.

[N] C.St.J. Nash-Williams, Decompositions of finite graphs into forests, J. London Math. Soc. 39 (1964) 12.

[T] W.T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956) 99-116.

Submitted by: Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA. (with thanks to Kedlaya)

Send comments to dan.archdeacon@uvm.edu

August, 1995. Modified November 1998