Simultaneous Embedding of a Planar Graph and Its Dual on the Grid

Details Simultaneous Embedding of a Planar Graph and Its Dual on the Grid Simultaneous Embedding of a Planar Graph and Its Dual on the Grid

2002-06-12

arxiv.org/abs/cs/0206019v1

Computer Science

Computational Geometry

14 pages, 8 figures

Scientific paper

Traditional representations of graphs and their duals suggest the requirement that the dual vertices be placed inside their corresponding primal faces, and the edges of the dual graph cross only their corresponding primal edges. We consider the problem of simultaneously embedding a planar graph and its dual into a small integer grid such that the edges are drawn as straight-line segments and the only crossings are between primal-dual pairs of edges. We provide a linear-time algorithm that simultaneously embeds a 3-connected planar graph and its dual on a (2n-2) by (2n-2) integer grid, where n is the total number of vertices in the graph and its dual. Furthermore our embedding algorithm satisfies the two natural requirements mentioned above.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-496543