2002/06/12 by Cesim Erten, C. Erten, Stephen Kobourov +3
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #F.2.2 #FOS: Computer and information sciences #G.2.2 #VLSI and FPGA Design Techniques #cs.CG
paper · pdf · doi:10.48550/arxiv.cs/0206019
14 pages, 8 figures
arxiv created 2002/06/12 · openalex publication_date 2002/06/12 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.