2010/01/04 by Patrizio Angelini, Markus Geyer, Angelini, Patrizio +5 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.1001.0555
openalex publication_date 2010/01/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.