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 , pp. 430-439(Official URL:

Full text not available from this repository.


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

Actions (login required)

View Item View Item