Partitions of Graphs into Trees

Biedl, Therese and Brandenburg, Franz J. (2007) Partitions of Graphs into Trees. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 430-439 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_41).

Full text not available from this repository.

Abstract

In this paper, we study the k-tree partition problem which is a partition of the set of edges of a graph into k edge-disjoint trees. This problem occurs at several places with applications e.g. in network reliability and graph theory. In graph drawing there is the still unbeaten (n-2) x (n-2) area planar straight line drawing of maximal planar graphs using Schnyder's realizers [15]}, which are a 3-tree partition of the inner edges. Maximal planar bipartite graphs have a 2-tree partition, as shown by Ringel [14]. Here we give a different proof of this result with a linear time algorithm. The algorithm makes use of a new ordering which is of interest of its own. Then we establish the NP-hardness of the k-tree partition problem for general graphs and k >= 2. This parallels NP-hard partition problems for the vertices [3], but it contrasts the efficient computation of partitions into forests (also known as arboricity) by matroid techniques [7].

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_41
Classifications:M Methods > M.900 Tree
P Styles > P.720 Straight-line
ID Code:798

Repository Staff Only: item control page

References

T. Biedl and F. J. Brandenburg. Drawing planar bipartite graphs with small area. In Proc. 17th Canadian Conference on Computational Geometry, CCCG'05, University of Windsor, Ontario, Canada, August 10-1, 2005, volume 17, 2005.

A. Brandstädt, V. B. Le, and T. Symczak. The complexity of some problems related to graph 3-colorability. Disc. Appl. Math., 89(1):59-73, 1998.

H. Broersma, F. V. Fomin, J. Kratochvil, and G. J. Woeginger. Planar graph coloring avoiding monochromatic subgraphs: Trees and paths make it difficult. Algorithmica, 44:343-361, 2006.

H. de Fraysseix, P. O. de Mendez, and J. Pach. Representation of planar graphs by segments. Intuitive Geometry, 63:109-117, 1991.

H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10:41-51, 1990.

S. Even and R. E. Tarjan. Computing an st-numbering. Theoretical Computer Science, 2:436-441, 1976.

H. N. Gabow and H. H. Westermann. Forests, frames, and games: Algorithms for matroid sums and applications. Algorithmica, 7:465-497, 1992.

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco, 1979.

G. Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16:4-32, 1996.

A. Lempel, S. Even, and I. Cederbaum. An algorithm for planarity testing of graphs. In Theory of Graphs, International Symposium Rome 1966, pages 215-232. Gordon and Breach, 1967.

C. S. J. Nash-Williams. Edge-disjoint spanning trees of finite graphs. J. London Math. Soc., 36:445-450, 1961.

C. S. J. Nash-Williams. Decomposition of finite graphs into forests. J. London Math. Soc., 39:12, 1964.

C. Papadimitriou. Computational Complexity. Addison Wesley, Reading MA, 1994.

G. Ringel. Two trees in maximal planar bipartite graphs. J. Graph Theory, 17:755-758, 1993.

W. Schnyder. Embedding planar graphs on the grid. In 1st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 138-148, 1990.