Schnyder's theorem

Short description: Order dimension of incidences in planar graphs

In graph theory, Schnyder's theorem is a characterization of planar graphs in terms of the order dimension of their incidence posets. It is named after Walter Schnyder, who published its proof in Schnyder|1989}}|1989.

The incidence poset P(G) of an undirected graph G with vertex set V and edge set E is the partially ordered set of height 2 that has V ∪ E as its elements. In this partial order, there is an order relation x < y when x is a vertex, y is an edge, and x is one of the two endpoints of y.

The order dimension of a partial order is the smallest number of total orderings whose intersection is the given partial order; such a set of orderings is called a realizer of the partial order. Schnyder's theorem states that a graph G is planar if and only if the order dimension of P(G) is at most three.

Extensions

This theorem has been generalized by Brightwell and Trotter (1993, 1997) to a tight bound on the dimension of the height-three partially ordered sets formed analogously from the vertices, edges and faces of a convex polyhedron, or more generally of an embedded planar graph: in both cases, the order dimension of the poset is at most four. However, this result cannot be generalized to higher-dimensional convex polytopes, as there exist four-dimensional polytopes whose face lattices have unbounded order dimension.

Even more generally, for abstract simplicial complexes, the order dimension of the face poset of the complex is at most 1 + d, where d is the minimum dimension of a Euclidean space in which the complex has a geometric realization (Ossona de Mendez 1999, 2002).

Other graphs

As Schnyder observes, the incidence poset of a graph G has order dimension two if and only if the graph is a path or a subgraph of a path. For, in when an incidence poset has order dimension is two, its only possible realizer consists of two total orders that (when restricted to the graph's vertices) are the reverse of each other. Any other two orders would have an intersection that includes an order relation between two vertices, which is not allowed for incidence posets. For these two orders on the vertices, an edge between consecutive vertices can be included in the ordering by placing it immediately following the later of the two edge endpoints, but no other edges can be included.

If a graph can be colored with four colors, then its incidence poset has order dimension at most four (Schnyder 1989).

The incidence poset of a complete graph on n vertices has order dimension [math]\displaystyle{ \Theta(\log\log n) }[/math] (Spencer 1971).

References

• Brightwell, G.; Trotter, W. T. (1993), "The order dimension of convex polytopes", SIAM Journal on Discrete Mathematics 6 (2): 230–245, doi:10.1137/0406018 .
• Brightwell, G.; Trotter, W. T. (1997), "The order dimension of planar maps", SIAM Journal on Discrete Mathematics 10 (4): 515–528, doi:10.1137/S0895480192238561 .
• Ossona de Mendez, P. (1999), "Geometric realization of simplicial complexes", in Kratochvil, J., Proc. Int. Symp. Graph Drawing (GD 1999), Lecture Notes in Computer Science, 1731, Springer-Verlag, pp. 323–332, doi:10.1007/3-540-46648-7_33 .
• Ossona de Mendez, P. (2002), "Realization of posets", Journal of Graph Algorithms and Applications 6 (1): 149–153, doi:10.7155/jgaa.00048, http://www.cs.brown.edu/publications/jgaa/accepted/2002/deMendez2002.6.1.pdf .
• Schnyder, W. (1989), "Planar graphs and poset dimension", Order 5 (4): 323–343, doi:10.1007/BF00353652 .
• "Minimal scrambling sets of simple orders", Acta Mathematica Academiae Scientiarum Hungaricae 22 (3–4): 349–353, 1971, doi:10.1007/bf01896428 .