**Dimension and
Outer-Planar Graphs**

Let G be a finite simple
connected graph of order at least 3. A nonempty family R of linear orders on the vertices
of G is called a realizer if for every edge xy and every vertex z, there is some L in R such that x < z and y < z. The dimension of G is equal to minimal cardinality
of R that realizes G. The concept is related to the
dimension of a poset, In particular:Schnyder [S] proved:

Theorem: A graph is planar if and only if the
dimension of its incident poset is at most 3.

Felsner and Trotter [FT] conjecture:

Conjecture: Dim(G) is at most 4 if and only if the
vertices can be partitioned into 4 parts such that each part induces an
outer-planar graph.

Felsner and Trotter proved that if the desired partition exists,
then the dimension is at most 4. The difficulty is in the converse.

Felsner and Trotter also introduced a fractional version of
dimension, and showed that a graph was outer-planar if and only if its
fractional dimension was at least 5/2. For details see [FT].

**References:**

[FT] S. Felsner and W.T. Trotter, Posets
and planar graphs, preprint

[S] W. Schnyder, Planar graphs and poset dimension, Order 5 (1989) 323-343

[S] W. Schnyder, Planar graphs and poset dimension, Order 5 (1989) 323-343

Submitted by: Dan Archdeacon, Dept. of Math.
and Stat.,

Send comments to *dan.archdeacon@uvm.edu*

December 2003