Convex Drawings of 3-Connected Plane Graphs

摘要

We use Schnyder woods of 3-connected planar graphs to produce convex straight-line drawings on a grid of size (n - 2 - Δ) x (n - 2 - Δ). The parameterΔ ≥ 0 depends on the Schnyder wood used for the drawing. This parameter is in the range 0 ≤ Δ ≤ n/2 - 2. The algorithm is a refinement of the face-counting algorithm; thus, in particular, the size of the grid is at most (f - 2) x (f - 2). The above bound on the grid size simultaneously matches or improves all previously known bounds for convex drawings, in particular Schnyder's and the recent Zhang and He bound for triangulations and the Chrobak and Kant bound for 3-connected planar graphs. The algorithm takes linear time. The drawing algorithm has been implemented and tested. The expected grid size for the drawing of a random triangulation is close to 7/8 x 7/8n. For a random 3-connected plane graph, tests show that the expected size of the drawing is 3/4n x 3/4n.