1996/01/01 by Marek Chrobák, Michael T. Goodrich, Roberto Tamassia · 65 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Topological and Geometric Data Analysis #Regular polygon #Computer science #Combinatorics #Mathematics #Geometry
paper · doi:10.1145/237218.237401
openalex publication_date 1996/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
In this paper, we investigate the area and volume requirement of convex drawings of planar graphs in two and three dimensions, under various resolution rules. Let G be a triconnected planar graph with n vertices. We provide O(n)-time algorithms for constructing the following types of drawings of G: ffl a 2D convex grid drawing of G with (3n) \Θ (3n=2) area under the edge resolution rule (in the L 1 metric). ffl a 2D strictly convex grid drawing of G with O(n 3 ) \Θ O(n 3 ) area under the edge resolution rule (in the L 1 metric). ffl a 2D strictly convex drawing of G with O(1) \Θ O(n) area under the vertex-resolution rule, and with vertex coordinates represented by O(n log n)-bit rational numbers; ffl a 3D convex drawing of G with O(1) ThetaO(1) ThetaO(n) volume under the vertex-resolution rule, and with vertex coordinates represented by O(n log n)-bit rational numbers. We also show the following lower bounds on the area/volume of 2D/3D convex drawings under the edg...