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 tool 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 follows: 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 the number of vertices. Every triconnected planar graph with maximum degree 4 admits a planar orthogonal grid drawing on an n x n grid with at 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 orthogonal grid drawing with at most [n/2] + 1 bends on an [n/2] x [n/2] grid. Every triconnected planar graph G admits a planar polyline grid drawing 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 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.