Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Eighteenth International Symposium on Graph Drawing, GD 2010
DOI: 10.7155/jgaa.00250
On a Tree and a Path with no Geometric Simultaneous Embedding
Vol. 16, no. 1, pp. 37-83, 2012. Regular paper.
Abstract Two graphs G1=(V,E1) and G2=(V,E2) admit a geometric simultaneous
embedding if there exist a set of points P and a bijection M: V→ P that induce planar straight-line embeddings both for G1
and for G2. The most prominent problem in this area is the question of
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 negatively answer another open question, that is, whether
it is 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.
|
Submitted: December 2010.
Reviewed: April 2011.
Revised: August 2011.
Reviewed: October 2011.
Revised: November 2011.
Accepted: November 2011.
Final: November 2011.
Published: January 2012.
|
Journal Supporters
|