en>Mark viking: Added context to first sentence

2013-09-20T22:21:10Z

Added context to first sentence

← Older revision		Revision as of 00:21, 21 September 2013
Line 1:		Line 1:
	~~Nice to satisfy you~~, ~~my name~~ is ~~Figures Held although I don~~'~~t truly like being~~ called ~~like that~~. ~~Since she was 18 she~~'s been ~~operating~~ as ~~a meter reader but she'~~s ~~always wanted her own company~~. ~~The factor she adores~~ most is ~~body developing~~ and ~~now she~~ is ~~attempting~~ to ~~make cash~~ with ~~it. South Dakota is exactly where me and my spouse live and my family loves it~~.<br><br>~~My web site~~ - [http://www.~~fuguporn~~.~~com~~/~~blog~~/~~36031 at home std testing~~]		In [[graph theory]], '''Schnyder's theorem''' is a characterization of [[planar graph]]s in terms
			of the [[order dimension]] of their incidence [[partially ordered set\|posets]]. It is named after Walter Schnyder, who published its proof in [[#{{harvid\|Schnyder\|1989}}\|1989]].

			The incidence poset {{math\|''P''(''G'')}} of an [[undirected graph]] {{mvar\|G}} with [[vertex (graph theory)\|vertex]] set {{mvar\|V}} and [[graph theory\|edge]] set {{mvar\|E}} is the [[partially ordered set]] of [[Antichain#Height and width\|height]] 2 that has {{math\|''V'' ∪ ''E''}} as its elements. In this partial order, there is an order relation {{math\|''x'' < ''y''}} when {{mvar\|x}} is a vertex, {{mvar\|y}} is an edge, and {{mvar\|x}} is one of the two endpoints of {{mvar\|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 {{mvar\|G}} is planar if and only if the order dimension of {{math\|''P''(''G'')}} is at most three.

			== Extensions ==
			This theorem has been generalized by {{harvs\|last1=Brightwell\|last2=Trotter\|year=1993\|year2=1997\|txt}} 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 polytope]]s, as there exist four-dimensional polytopes whose [[face lattice]]s 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 {{math\|1 + ''d''}}, where {{mvar\|d}} is the minimum dimension of a [[Euclidean space]] in which the complex has a geometric realization {{harvs\|last=Ossona de Mendez\|year=1999\|year2=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, the only possible realizer for the incidence poset consists of two total orders that (when restricted to the graph's vertices) are the reverse of each other; otherwise, the intersection of the two orders would include an order relation between two vertices, which is not allowed for incidence posets. But two total orders on the vertices that are the reverse of each other can realize any subgraph of a path, by including the edges of the path in the ordering immediately following the later of the two edge endpoints.

			If a graph can be [[graph coloring\|colored]] with four colors, then its incidence poset has order dimension at most four {{harv\|Schnyder\|1989}}.

			The incidence poset of a [[complete graph]] on ''n'' vertices has order dimension <math>\Theta(\log\log n)</math> {{harv\|Spencer\|1971}}.

			== References ==
			*{{citation\|first1=G.\|last1=Brightwell\|first2=W. T.\|last2=Trotter\|title=The order dimension of convex polytopes\|journal=[[SIAM Journal on Discrete Mathematics]]\|volume=6\|year=1993\|pages=230–245\|doi=10.1137/0406018\|issue=2\|mr=1215230}}.
			*{{citation\|first1=G.\|last1=Brightwell\|first2=W. T.\|last2=Trotter\|title=The order dimension of planar maps\|journal=[[SIAM Journal on Discrete Mathematics]]\|volume=10\|year=1997\|issue=4\|pages=515–528\|doi=10.1137/S0895480192238561\|mr=1477654}}.
			*{{citation\|first=P.\|last=Ossona de Mendez\|contribution=Geometric realization of simplicial complexes\|editor-first=J.\|editor-last=Kratochvil\|title=[[International Symposium on Graph Drawing\|Proc. Int. Symp. Graph Drawing (GD 1999)]]\|volume=1731\|series=Lecture Notes in Computer Science\|publisher=Springer-Verlag\|pages=323–332\|year=1999\|doi=10.1007/3-540-46648-7_33\|mr=1856785}}.
			*{{citation\|first=P.\|last=Ossona de Mendez\|url=http://www.cs.brown.edu/publications/jgaa/accepted/2002/deMendez2002.6.1.pdf\|title=Realization of posets\|journal=[[Journal of Graph Algorithms and Applications]]\|volume=6\|issue=1\|pages=149–153\|year=2002\|mr=1898206}}.
			*{{citation\|first=W.\|last=Schnyder\|title=Planar graphs and poset dimension\|journal=[[Order (journal)\|Order]]\|volume=5\|year=1989\|pages=323–343\|doi=10.1007/BF00353652\|mr=1010382}}.
			*{{citation
			\| last = Spencer \| first = J. \| authorlink = Joel Spencer
			\| journal = Acta Mathematica Academiae Scientiarum Hungaricae
			\| mr = 0292722
			\| pages = 349–353
			\| title = Minimal scrambling sets of simple orders
			\| volume = 22
			\| year = 1971}}.

			[[Category:Order theory]]
			[[Category:Planar graphs]]
			[[Category:Theorems in graph theory]]

en>Helpful Pixie Bot: ISBNs (Build KG)

2012-05-11T20:16:50Z

ISBNs (Build KG)

New page

Nice to satisfy you, my name is Figures Held although I don't truly like being called like that. Since she was 18 she's been operating as a meter reader but she's always wanted her own company. The factor she adores most is body developing and now she is attempting to make cash with it. South Dakota is exactly where me and my spouse live and my family loves it.<br><br>My web site - [http://www.fuguporn.com/blog/36031 at home std testing]

Sample exclusion dimension - Revision history

en>Mark viking: Added context to first sentence

en>Helpful Pixie Bot: ISBNs (Build KG)