Schnyder's theorem

Schnyder's theorem

In mathematics, Schnyder's theorem in graph theory is a planarity characterization for graphs in termsof 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 Vcup E, where x if 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 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.

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.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Schnyder — is used in Switzerland as an alternative spelling of the more common German surname Schneider (tailor). Immigrants to North America often spelled their name as Snyder.* Patty Schnyder (born 1978), Swiss tennis player * Josef Schnyder (born 1923) …   Wikipedia

  • Fáry's theorem — states that any simple planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straight line segments does not allow a larger class of graphs to be …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Planar graph — Example graphs Planar Nonplanar Butterfly graph K5 The complete graph K4 …   Wikipedia

  • Order dimension — A partial order of dimension 4 (shown as a Hasse diagram) and four total orderings that form a realizer for this partial order. In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”