Two graphs G_1 = (V, E_1) and G_2 = (V, E_2) 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 G_1 and for G_2. The most prominent problem in this area is the question whether a tree and a path can always be simultaneously embedded. 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 prove that it is not always possible to simultaneously embed two edge-disjoint trees. Finally, we study the same problem when some constraints on the tree are imposed. Namely, we show that a tree of height 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 height 4.
展开▼
