Drawing planar graphs using the canonical ordering

Abstract

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. Using this method linear time and space algorithms can be designed for many graph drawing problems. Every triconnected planar graph G can be drawn convexly with straight lines on an (2n -4) x (n-2) grid, where n is the number of vertices. Every triconnected planar graph with maximum degree four can be drawn orthogonally on an n x n grid with at most [3n/2] + 4, and if n>6 then every edge has at most two bends. Every 3-planar graph G can be drawn with at most [n/2] + 1 bends on an [n/2] x [n/2] grid. Every triconnected planar graph G can be drawn planar on an (2n-6) x (3n-9) grid with minimum angle larger than 2/4 radians and at most 5n-15 bends, with d the maximum degree. There is a new method for constructing a visibility representation of a planar graph on a grid of size at most (2n-s) x (n-1). 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.