DRAWING PLANAR GRAPHS USING THE CANONICAL ORDERING

We introduce a new method to optimize the required area, minimum angle , and number of bends of planar graph drawings on a grid. The main too l is a new type of ordering on the vertices and faces of triconnected planar graphs. Using this method linear-time-and-space algorithms can be designed for many graph-drawing problems. Our main results are as f ollows: Every triconnected planar graph G admits a planar convex grid drawing with straight lines on a (2n - 4) x (n - 2) grid, where n is t he number of vertices. Every triconnected planar graph with maximum de gree 4 admits a planar orthogonal grid drawing on an n x n grid with a t most [3n/2] + 4 bends, and if n > 6, then every edge has at most two bends. Every planar graph with maximum degree 3 admits a planar ortho gonal grid drawing with at most [n/2] + 1 bends on an [n/2] x [n/2] gr id. Every triconnected planar graph G admits a planar polyline grid dr awing on a (2n - 6) x (3n - 9) grid with minimum angle larger than 2/d radians and at most 5n - 15 bends, with d the maximum degree. These r esults give in some cases considerable improvements over previous resu lts, and give new bounds in other cases. Several other results, e.g., concerning visibility representations, are included.