On a Tree and a Path with no Geometric Simultaneous Embedding

Details On a Tree and a Path with no Geometric Simultaneous Embedding On a Tree and a Path with no Geometric Simultaneous Embedding

2010-01-04

arxiv.org/abs/1001.0555v1

Computer Science

Computational Geometry

42 pages, 33 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On a Tree and a Path with no Geometric Simultaneous Embedding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On a Tree and a Path with no Geometric Simultaneous Embedding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On a Tree and a Path with no Geometric Simultaneous Embedding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-7587