슈니더의 정리 문서 원본 보기

{{위키데이터 속성 추적}}
'''슈니더의 정리'''(Schnyder's theorem, -定理)은 [[그래프 이론]]의 [[정리]]로, [[평면 그래프]]의 특성화를 위한 조건을 제공한다.

== 정의 ==
[[그래프]] <math>G</math>에 대하여, '''인접 부분 순서 집합'''({{llang|en|incidence poset}}) <math>P(G)</math>는 집합으로서 [[분리합집합]]<math>P(G)=V(G)\sqcup E(G)</math>이며, 다음과 같은 [[부분 순서]]를 갖는다.
:<math>u\le uv\qquad\forall uv\in E(G)</math>
즉, 변 <math>uv</math>는 그 양끝점보다 더 크다.

'''슈니더의 정리'''에 따르면, 유한 [[그래프]] <math>G</math>에 대하여 다음 두 조건이 서로 [[동치]]이다.
* <math>G</math>는 [[평면 그래프]]이다.
* <math>P(G)</math>의 [[순서 차원]] ([[교집합]]이 해당 부분순서가 되는 [[전순서]]들의 최소 수)은 3 이하이다.

== 확장 ==
슈니더의 정리는 임의의 차원으로 확장할 수 있다.(Ossona de Mendez 1999, 2002) 일반적으로, 임의의 [[추상 복체]](abstract simplical complex)에 대하여 이 추상 복체가 적어도 d차원 [[유클리드 공간]]에서야 기하학적으로 구현(realization)된다면, 그 면과 꼭짓점으로 위의 방법과 같이 유도한 부분 순서 집합이 많아야 1+d의 순서 차원을 가진다. 슈니더의 정리는 이 확장 형태에서 d=2인 경우이다.

== 역사 ==
[[스위스]]의 수학자 발터 슈니더({{llang|de|Walter Schnyder}})가 [[1989년]]에 증명하였다.<ref>Schnyder, W. (1989), "Planar graphs and poset dimension", ''Order'' '''5''': 323–343, [http://dx.doi.org/10.1007%2FBF00353652 doi:10.1007/BF00353652], MR [http://www.ams.org/mathscinet-getitem?mr=1010382 1010382].</ref>

== 각주 ==
{{각주}}
* Brightwell, G.; Trotter, W. T. (1993), "The order dimension of convex polytopes", ''SIAM Journal on Discrete Mathematics'' '''6''' (2): 230–245, doi:10.[http://dx.doi.org/10.1137%2F0406018 1137/0406018], MR [http://www.ams.org/mathscinet-getitem?mr=1215230 1215230].
* Brightwell, G.; Trotter, W. T. (1997), "The order dimension of planar maps", ''SIAM Journal on Discrete Mathematics'' '''10''' (4): 515–528, doi:[http://dx.doi.org/10.1137%2FS0895480192238561 10.1137/S0895480192238561], MR [http://www.ams.org/mathscinet-getitem?mr=1477654 1477654].
* Ossona de Mendez, P. (1999), "Geometric realization of simplicial complexes", in Kratochvil, J., ''Proc. Int. Symp. Graph Drawing (GD 1999)'', Lecture Notes in Computer Science, '''1731''', Springer-Verlag, pp.&nbsp;323–332, doi:[http://dx.doi.org/10.1007%2F3-540-46648-7_33 10.1007/3-540-46648-7_33], MR [http://www.ams.org/mathscinet-getitem?mr=1856785 1856785].
* Ossona de Mendez, P. (2002), [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, [http://www.ams.org/mathscinet-getitem?mr=1898206 MR1898206].

[[분류:순서론]]
[[분류:그래프 이론 정리]]
[[분류:평면 그래프]]