Planar Packing of Binary Trees

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

T

1

and

T

2

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

T

i

, 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.