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
email: felsner@inf.fu-berlin.de
Report B-00-15
2000
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:
Server: ftp.inf.fu-berlin.de
File: pub/reports/tr-b-00-15.ps.gz