Decomposing $4$-connected planar triangulations into two trees and one path

Abstract

Refining a classical proof of Whitney, we show that any $4$-connected planar triangulation can be decomposed into a Hamiltonian path and two trees. Therefore, every $4$-connected planar graph decomposes into three forests, one having maximum degree at most $2$. We use this result to show that any Hamiltonian planar triangulation can be decomposed into two trees and one spanning tree of maximum degree at most $3$. These decompositions improve the result of Gonçalves [Covering planar graphs with forests, one having bounded maximum degree. J. Comb. Theory, Ser. B, 100(6):729--739, 2010] that every planar graph can be decomposed into three forests, one of maximum degree at most $4$. We also show that our results are best-possible.

22 pages, 10 figures