An automatic layout facility (abstract)
Giuseppe Liotta · ACM SIGACT News · 1993
We introduce a new method to optimize the required area, minimum angle and number of bends of planar drawings of graphs on a grid. The main tool is a new type of ordering on the vertices and faces of triconnected planar graphs. With this method linear time an space algorithms can be designed for many graph drawing problems. (i) We show that every triconnected planar graph G can be drawn convexly with straight lines on an (2 n -4)×( n -2) grid. (ii) If G has maximum degree four (three), then G can be drawn orthogonal with at most [3 n /2] + 3 (at most [ n /2] + 1) bends on an n × n grid ([ n /2] × [ n /2] grid, respectively). (iii) If G has maximum degree d , then G can be drawn planar on an (2 n -6) × (3 n -6) grid with minimum angle larger than 1/d-2 radians and at most 5 n -15 bends. These results give in some cases considerable improvements over previous results, and give new bounds in other cases. Several other results, e.g. concerning visibility representations, are included.