- Schnyder's theorem
In
mathematics , Schnyder's theorem ingraph theory is a planarity characterization for graphs in termsof theorder dimension of their incidence posets.The incidence poset P(G) of a graph "G" with vertex set "V" and edge set "E" is the
partially ordered set of height 2 on Vcup E, where xif xin V, yin E and y is incident to x. Schnyder's theorem states that a graph "G" is planar if and only if
:dim P(G)leq 3.
Extensions
This theorem has been generalized by Brightwell and Trotter to a characterization of the dimension of the vertex, edges and faces posets of planar graphs, and to a generalization to
multigraph s.Although the generalization of Schnyder's result to the problem of the geometric realization of an abstract
simplicial complex is quite natural and may be viewed as the existence of embeddings of posets inEuclidean space with a general separation property, the property of being minor closed disappears in dimension at least 4.References
* G. Brightwell and W.T. Trotter, "The order dimension of convex polytopes", SIAM Journal of Discrete Mathematics 6 (1993), 230-245.
* G. Brightwell and W.T. Trotter, "The order dimension of planar maps", SIAM journal on Discrete Mathematics 10 (1997), no. 4, 515-528.
* P. Ossona de Mendez. "Geometric Realization of Simplicial Complexes". In J. Kratochvil, editor, Proc. Int. Symp. Graph Drawing (GD 1999), volume 1731 of Lecture Notes in Computer Science, pages 323-332. Springer, 1999.
* P. Ossona de Mendez. " [http://www.cs.brown.edu/publications/jgaa/accepted/2002/deMendez2002.6.1.pdf Realization of posets] ". Journal of Graph Algorithms and Applications, 6(1):149-153, 2002.
* W. Schnyder, "Planar graphs and poset dimension", Order 5 (1989), 323--343.
Wikimedia Foundation. 2010.