On a Tree and a Path with no Geometric Simultaneous Embedding - Angelini, Patrizio; Geyer, Markus; Kaufmann, Michael; Neuwirth, Daniel (Journal of Graph Algorithms and Applications, 2012)
Two graphs G1=(V,E1) and G2=(V,E2) admit a geometric simultaneousembedding if there exist a set of points P and a bijection M: V→ P that induce planar straight-line embeddings both for G1and for G2. The most prominent problem in this area is the question ofwhether 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 twographs, we also negatively answer another open question, that is, whetherit is possible to simultaneously embed two edge-disjoint trees. Finally, westudy 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 ageometric simultaneous embedding. In fact, such a strong constraint is notso far from closing the gap with the instances not admitting any solution,as the tree used in our counterexample has height 4. <!---->