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
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].
Submitted by: Dan Archdeacon, Dept. of Math.
Send comments to firstname.lastname@example.org