On Simultaneous Graph Embedding

Details On Simultaneous Graph Embedding On Simultaneous Graph Embedding

2002-06-11

arxiv.org/abs/cs/0206018v3

Computer Science

Computational Geometry

12 pages, 4 figures

Scientific paper

We consider the problem of simultaneous embedding of planar graphs. There are two variants of this problem, one in which the mapping between the vertices of the two graphs is given and another where the mapping is not given. In particular, we show that without mapping, any number of outerplanar graphs can be embedded simultaneously on an $O(n)\times O(n)$ grid, and an outerplanar and general planar graph can be embedded simultaneously on an $O(n^2)\times O(n^3)$ grid. If the mapping is given, we show how to embed two paths on an $n \times n$ grid, a caterpillar and a path on an $n \times 2n$ grid, or two caterpillar graphs on an $O(n^2)\times O(n^3)$ grid. We also show that 5 paths, or 3 caterpillars, or two general planar graphs cannot be simultaneously embedded given the mapping.

Affiliated with

Also associated with

No associations

Rating

On Simultaneous Graph 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 Simultaneous Graph Embedding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Simultaneous Graph Embedding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-496539