Paper Info
Title
Planar packing of binary trees
Abstract
In the graph packing problem we are given several graphs and have to map them into a single host graph G such that each edge of G is used at most once. Much research has been devoted to the packing of trees, especially to the case where the host graph must be planar. More formally, the problem is: Given any two trees T1 and T2 on n vertices, we want a simple planar graph G on n vertices such that the edges of G can be colored with two colors and the subgraph induced by the edges colored i is isomorphic to Ti, for i∈{1,2}. A clear exception that must be made is the star tree which cannot be packed together with any other tree. But a popular hypothesis states that this is the only exception, and all other pairs of trees admit a planar packing. Previous proof attempts lead to very limited results only, which include a tree and a spider tree, a tree and a caterpillar, two trees of diameter four and two isomorphic trees. We make a step forward and prove the hypothesis for any two binary trees. The proof is algorithmic and yields a linear time algorithm to compute a plane packing, that is, a suitable two-edge-colored host graph along with a planar embedding for it. In addition we can also guarantee several nice geometric properties for the embedding: vertices are embedded equidistantly on the x-axis and edges are embedded as semi-circles.
Year
DOI
Venue
2013
10.1007/978-3-642-40104-6_31
WADS
Keywords
Field
DocType
star tree,isomorphic tree,n vertex,binary tree,trees T1,host graph,planar packing,single host graph,spider tree,simple planar graph,graph packing problem
Pseudoforest,Discrete mathematics,Combinatorics,Trémaux tree,Tree (graph theory),Graph embedding,Planar straight-line graph,Multiple edges,Planar graph,Mathematics,Path graph
Conference
Citations 
PageRank 
References 
1
0.38
14
Authors
5
Name
Order
Citations
PageRank
Markus Geyer1747.26
Michael Hoffmann222722.74
Michael Kaufmann336125.45
Vincent Kusters4316.31
Csaba D. Tóth557370.13