# Posets and Planar Graphs

###
Stefan Felsner

Institut für Informatik

Freie Universität Berlin

Takustr. 9, D-14195 Berlin

email: felsner@inf.fu-berlin.de

William T. Trotter

Department of Mathematics

Arizona State University

Tempe, Arizona 85287-1804 U.S.A.

email: trotter@ASU.edu

Report B 98-11

August 1998

In 1989, W. Schnyder proved that a graph is planar if and only if its dimension is at most 3. Although dimension is an integer valued parameter, we introduce a fractional version of dimension and show that a graph is outerplanar if and only if its dimension is at most 5/2. Extending recent work of Hos¸ten and Morris, we show that the largest *n* for which the dimension of the complete graph *K*_{n} is at most *t* - ½ is the number of antichains in the lattice of all subsets of a set of size *t* - 2. Accordingly, this dimension problem for complete graphs is equivalent to the classical combinatorial problem known as Dedekind's problem. For *t* = 4 we show that any graph for which the vertex set can be partitioned into *2* parts so that each part induces an outerplanar graph has dimension at most 7/2, and we conjecture that this is a full characterization of such graphs. This characterization was discovered in the course of research on an extremal graph theory problem posed by Agnarsson: Find the maximum number of edges in a graph on *n* nodes with dimension at most *t*.

Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-98-11.ps.gz