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


Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of Vermont, Burlington, VT 05401-1455 USA

Send comments to dan.archdeacon@uvm.edu

December 2003