Advertisement
Published in:
2007 | OriginalPaper | Chapter
Partitions of Graphs into Trees
Authors : Therese Biedl, Franz J. Brandenburg
Published in: Graph Drawing
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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) ×(
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].