On a Tree and a Path with no Geometric Simultaneous Embedding
| Autor: | Angelini, Patrizio, Geyer, Markus, Kaufmann, Michael, Neuwirth, Daniel |
|---|---|
| Rok vydání: | 2010 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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$. 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. Comment: 42 pages, 33 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|