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