Schnyder's Theorem

In graph theory, Schnyder's theorem is a characterization of planar graphs in terms of the order dimension of their incidence posets. It is named after Walter Schnyder, who published its proof in 1989.

The incidence poset P(G) of an undirected graph G with vertex set V and edge set E is the partially ordered set of height 2 that has VE as its elements. In this partial order, there is an order relation x < y when x is a vertex, y is an edge, and x is one of the two endpoints of y.

The order dimension of a partial order is the smallest number of total orderings whose intersection is the given partial order; such a set of orderings is called a realizer of the partial order. Schnyder's theorem states that a graph G is planar if and only if the order dimension of P(G) is at most three.

Read more about Schnyder's TheoremExtensions, Other Graphs

Other articles related to "schnyder":

Schnyder - See Also
... Schnyder's theorem in mathematics Schneider (disambiguation) Snyder (disambiguation) This page or section lists people with the surname Schnyder ...
Patty Schnyder - Career
... In 1996, Schnyder made her Grand Slam main-draw debut at the French Open ... However, Schnyder fell out of the top 10 in April 1999, and spent the next six years ranked in the 15–30 range before re-entering the top 10 in May 2005 ... In December 2003, Schnyder married Rainer Hofmann, who had accompanied her on the WTA tour since 1999 and became her full-time tennis coach in early 2003 ...
2009 Fed Cup World Group II - Switzerland Vs. Germany
... Ace (indoors) Germany 1 ... Patty Schnyder Anna-Lena Grönefeld 2 ... Timea Bacsinszky Sabine Lisicki 3 ... Patty Schnyder Sabine Lisicki 4 ... Timea Bacsinszky Anna-Lena Grönef ...
Switzerland At The 2004 Summer Olympics - Tennis
... Tennis tournament, but did not make a single quarterfinal, and only Patty Schnyder made the third round ... Patty Schnyder may not have earned a medal, but did earn bragging rights over Daniela Hantuchová, as she beat her in both the singles' and doubles' events, though in each case Schnyder was ... Singles Myriam Casanova First Round Lost to Nicole Pratt of Australia (3 - 6, 5 - 7) (10) Patty Schnyder First Round Defeated Petra Mandula of Hungary (6 - 3, 6 - 4) Second Round ...
2009 Sony Ericsson Open – Women's Doubles - Draw - Top Half
7 4 ... S Stosur R Stubbs 6 ... A-L Grönefeld P Schnyder 3 ... Z Yan J Zheng 4 ... S Stosur R Stubbs 7 ... A Pavlyuchenkova E Vesnina 6 ... A Pavlyuchenkova E Vesnina 64 ... L Hradecká V Uhlířová 4 ... S Stosur R ...

Famous quotes containing the word theorem:

    To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.
    Albert Camus (1913–1960)