Edge covering pseudo-outerplanar graphs with forests

A graph is pseudo-outerplanar if each block has an embedding on the plane in such a way that the vertices lie on a fixed circle and the edges lie inside the disk of this circle with each of them crossing at most one another. In this paper, we prove that each pseudo-outerplanar graph admits edge decompositions into a linear forest and an outerplanar graph, or a star forest and an outerplanar graph, or two forests and a matching, or max {Delta(G), 4} matchings, or max{inverted right perpendicular Delta(G)/2 inverted left perpendicular, 3} linear forests. These results generalize known results on outerplanar graphs and K-2,K-3-minor-free graphs, since the class of pseudo-outerplanar graphs is larger than the class of K-2,K-3-minor-free graphs. (C) 2012 Elsevier B.V. All rights reserved.