On a Tree and a Path with No Geometric Simultaneous Embedding

Angelini, 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 21-24, 2010 , pp. 38-49(Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_4).

Full text not available from this repository.


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 --> A  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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-18469-7_4
Classifications: G Algorithms and Complexity > G.490 Embeddings
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1192

Actions (login required)

View Item View Item