mathematics

Schnyder's theorem

Schnyder's theorem is a mathematics topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Schnyder's theorem rather than just read about it. In short: 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.

Key takeaways

Schnyder's theorem belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Schnyder's theorem to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Schnyder's theorem from memory before moving on to harder problems.

Reference excerpt

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 V ∪ E 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.

Extensions This theorem has been generalized by Brightwell and Trotter (1993, 1997) 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 polytopes, as there exist four-dimensional polytopes whose face lattices have unbounded order dimension. Even more generally, for abstract simplicial complexes, the order dimension of the face poset of the complex is at most 1 + d, where d is the minimum dimension of a Euclidean space in which the complex has a geometric realization (Ossona de Mendez 1999, 2002).

Other graphs As Schnyder observes, the incidence poset of a graph G has order dimension two if and only if the graph is a path or a subgraph of a path. For, when an incidence poset has order dimension two, its only possible realizer consists of two total orders that (when restricted to the graph's vertices) are the reverse of each other. Any other two orders would have an intersection that includes an order relation between two vertices, which is not allowed for incidence posets. For these two orders on the vertices, an edge between consecutive vertices can be included in the ordering by placing it immediately following the later of the two edge endpoints, but no other edges can be included. If a graph can be colored with four colors, then its incidence poset has order dimension at most four (Schnyder 1989). The incidence poset of a complete graph on n vertices has order dimension Θ ( log ⁡ log ⁡ n ) {\displaystyle \Theta (\log \log n)} (Spencer 1971).

References Brightwell, G.; Trotter, W. T. (1993), "The order dimension of convex polytopes", SIAM Journal on Discrete Mathematics, 6 (2): 230–245, doi:10.1137/0406018, MR 1215230. Brightwell, G.; Trotter, W. T. (1997), "The order dimension of planar maps", SIAM Journal on Discrete Mathematics, 10 (4): 515–528, CiteSeerX 10.1.1.127.1016, doi:10.1137/S0895480192238561, MR 1477654 {{citation}}: Cite uses deprecated parameter |citeseerx= (help). Ossona de Mendez, P. (1999), "Geometric realization of simplicial complexes", in Kratochvil, J. (ed.), Proc. Int. Symp. Graph Drawing (GD 1999), Lecture Notes in Computer Science, vol. 1731, Springer-Verlag, pp. 323–332, doi:10.1007/3-540-46648-7_33, ISBN 978-3-540-66904-3, MR 1856785. Ossona de Mendez, P. (2002), "Realization of posets" (PDF), Journal of Graph Algorithms and Applications, 6 (1): 149–153, doi:10.7155/jgaa.00048, MR 1898206. Schnyder, W. (1989), "Planar graphs and poset dimension", Order, 5 (4): 323–343, doi:10.1007/BF00353652, MR 1010382, S2CID 122785359. Spencer, J. (1971), "Minimal scrambling sets of simple orders", Acta Mathematica Academiae Scientiarum Hungaricae, 22 (3–4): 349–353, doi:10.1007/bf01896428, MR 0292722, S2CID 123142998.

Worked examples

Example 1 — a first encounter with Schnyder's theorem

Start with the simplest possible case. Write down what Schnyder's theorem claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Schnyder's theorem before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Schnyder's theorem ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Schnyder's theorem

In research: Schnyder's theorem appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Schnyder's theorem in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Schnyder's theorem is common in secondary-school and first-year university syllabi. It links to neighbouring topics Order theory, Statements about planar graphs, Theorems in graph theory, so understanding it makes those chapters shorter.
In everyday life: Look for Schnyder's theorem outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Schnyder's theorem” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Schnyder's theorem in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Schnyder's theorem means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Schnyder's theorem out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Schnyder's theorem in simple terms?

Why does Schnyder's theorem matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Schnyder's theorem?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Schnyder's theorem.