Schnyder's theorem
Encyclopedia
In graph theory
, Schnyder's theorem is a characterization of planar graph
s in terms
of the order dimension
of their incidence posets
. It is named after Walter Schnyder, who published its proof in Schnyder.
The incidence poset of an undirected graph with vertex
set and edge
set is the partially ordered set
of height 2 that has as its elements. In this partial order, there is an order relation when is a vertex, is an edge, and is one of the two endpoints of .
The order dimension of a partial order is the smallest number of total orderings whose intersection is the given partial order.
Schnyder's theorem states that a graph is planar if and only if the order dimension of is at most three.
s, as there exist four-dimensional polytopes whose face lattices have unbounded order dimension.
Even more generally, for abstract simplicial complex
es, the order dimension of the face poset of the complex is at most , where is the minimum dimension of a Euclidean space
in which the complex has a geometric realization .
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, Schnyder's theorem is a characterization of planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
s in terms
of the order dimension
Order dimension
In mathematics, the dimension of a partially ordered set is the smallest number of total orders the intersection of which gives rise to the partial order....
of their incidence posets
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
. It is named after Walter Schnyder, who published its proof in Schnyder.
The incidence poset of an undirected graph with vertex
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
set and edge
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
set is the partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
of height 2 that has as its elements. In this partial order, there is an order relation when is a vertex, is an edge, and is one of the two endpoints of .
The order dimension of a partial order is the smallest number of total orderings whose intersection is the given partial order.
Schnyder's theorem states that a graph is planar if and only if the order dimension of is at most three.
Extensions
This theorem has been generalized by 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 polytopeConvex polytope
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set of points in the n-dimensional space Rn...
s, as there exist four-dimensional polytopes whose face lattices have unbounded order dimension.
Even more generally, for abstract simplicial complex
Abstract simplicial complex
In mathematics, an abstract simplicial complex is a purely combinatorial description of the geometric notion of a simplicial complex, consisting of a family of finite sets closed under the operation of taking subsets...
es, the order dimension of the face poset of the complex is at most , where is the minimum dimension of a Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
in which the complex has a geometric realization .