|
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 , where x < y if , and y is incident to x.
Schnyder's theorem states that a graph G is planar if and only if
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.
|
