Abstract. Two graphs G1 = (V, E1) and G2 = (V, E2) admit a geometric simultaneous embedding if there exists a set of points P and a bijection M : P → V that induce planar straight-line embeddings both for G1 and for G2. While it is known that two caterpillars always admit a geometric simultaneous embedding and that two trees not always admit one, the question about a tree and a path is still open and is often regarded as the most prominent open problem in this area. We answer this question in the negative by providing a counterexample. Additionally, since the counterexample uses disjoint edge sets for the two graphs, we also negatively answer another open question, that is, whether it is possible to simultaneously embed two edge-disjoint trees. As a final result, we study the same problem when some constraints on the tree are imposed. Namely, we show that a tree of depth 2 and a path always admit a geometric simultaneous embedding. In fact, such a strong constraint is not so far from closing the gap with the instances not admitting any solution, as the tree used in our counterexample has depth 4.
Angelini et al. REF proved the same result for a path and a tree.
On a Tree and a Path with no Geometric Simultaneous Embedding
ArXiv
ArXiv
Computer Science Mathematics