## 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