Tight planar packings of two trees
Yoshiaki Oda, Katsuhiro Ota · 2006
When we consider an embedding of graphs into a plane, it would be nice if it does not intersect internally since the embedding simply shows us the structure of graphs. It is easy to embed a tree into a plane with non-self-intersections. If we embed two or more trees into a plane with non-self-intersections, what occurs? In this paper, we consider embeddings of two trees into a plane with using same vertices, sharing no edges and no-intersections. We prove that a non-star tree and a non-star caterpillar can be embedded into a plane satisfying the above conditions. It is one of the special cases of a conjecture by Garcia et al. [1].