TY - JOUR
T1 - Simultaneous embedding of a planar graph and its dual on the grid
AU - Erten, Cesim
AU - Kobourov, Stephen G.
N1 - Funding Information:
∗ This research was partially supported by NSF Grant ACR-0222920.
PY - 2005/5
Y1 - 2005/5
N2 - Traditional representations of graphs and their duals suggest that the dual vertices should be placed inside their corresponding primal faces, and the edges of the dual graph should only cross their corresponding primal edges. We consider the problem of simultaneously embedding a planar graph and its dual on 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 an O(n) time algorithm that simultaneously embeds a 3-connected planar graph and its dual on a (2n - 2) × (2n - 2) integer grid, where n is the total number of vertices in the graph and its dual. All the edges are drawn as straight-line segments except for one edge on the outer face, which is drawn using two segments.
AB - Traditional representations of graphs and their duals suggest that the dual vertices should be placed inside their corresponding primal faces, and the edges of the dual graph should only cross their corresponding primal edges. We consider the problem of simultaneously embedding a planar graph and its dual on 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 an O(n) time algorithm that simultaneously embeds a 3-connected planar graph and its dual on a (2n - 2) × (2n - 2) integer grid, where n is the total number of vertices in the graph and its dual. All the edges are drawn as straight-line segments except for one edge on the outer face, which is drawn using two segments.
UR - http://www.scopus.com/inward/record.url?scp=18244373185&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=18244373185&partnerID=8YFLogxK
U2 - 10.1007/s00224-005-1143-4
DO - 10.1007/s00224-005-1143-4
M3 - Article
AN - SCOPUS:18244373185
SN - 1432-4350
VL - 38
SP - 313
EP - 327
JO - Theory of Computing Systems
JF - Theory of Computing Systems
IS - 3
ER -