Convex drawings of Planar Graphs and the Order Dimension of 3-Polytopes

Stefan Felsner
Institut für Informatik
Freie Universität Berlin
Takustr. 9, D-14195 Berlin

Report B-00-15

We define an analogue of Schnyder's tree decompositions for 3-connected planar graphs. Based on this structure we obtain:

  • Let G be a 3-connected planar graph with f faces, then G has a convex drawing with its vertices embedded on the (f-1)x(f-1) grid.
  • Let G be a 3-connected planar graph. The dimension of the incidence order of vertices, edges and bounded faces of G is at most 3.

    The second result is originally due to Brightwell and Trotter. Here we give a substantially simpler proof.
    Get the report here or by anonymous ftp:
    File:   pub/reports/