Convex drawings of graphs in two and three dimensions (preliminary version)
Marek Chrobák, Michael T. Goodrich, Roberto Tamassia · 1996
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) \\Theta (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 ) \\Theta 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) \\Theta 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...