Schnyder's theorem

From Wikipedia, the free encyclopedia

In mathematics, Schnyder's theorem in graph theory is a planarity characterization for graphs in terms of the order 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 $V\cup E$ , where $x < y$ if $x\in V$ , $y\in 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$ .

[edit] 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 multigraphs.

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 in Euclidean space with a general separation property, the property of being minor closed disappears in dimension at least 4.

[edit] 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. 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.