On a Tree and a Path with No Geometric Simultaneous EmbeddingAngelini, Patrizio and Geyer, Markus and Kaufmann, Michael and Neuwirth, Daniel (2011) On a Tree and a Path with No Geometric Simultaneous Embedding. In: Graph Drawing 18th International Symposium, GD 2010, September 2124, 2010 , pp. 3849(Official URL: http://dx.doi.org/10.1007/9783642184697_4). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783642184697_4
AbstractTwo 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 > A that induce planar straightline 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 edgedisjoint 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.
Actions (login required)
