슈니더의 정리

슈니더의 정리(Schnyder's theorem, -定理)은 그래프 이론의 정리로, 평면 그래프의 특성화를 위한 조건을 제공한다.

 정의 
그래프 에 대하여, 인접 부분 순서 집합() 는 집합으로서 분리합집합이며, 다음과 같은 부분 순서를 갖는다.

즉, 변 는 그 양끝점보다 더 크다.

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

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

 역사 
스위스의 수학자 발터 슈니더()가 1989년에 증명하였다.Schnyder, W. (1989), "Planar graphs and poset dimension", Order 5: 323–343, doi:10.1007/BF00353652, MR 1010382.

 각주 

 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, doi:10.1137/S0895480192238561, MR 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. 323–332, doi:10.1007/3-540-46648-7_33, MR 1856785.
 Ossona de Mendez, P. (2002), "Realization of posets" , Journal of Graph Algorithms and Applications 6 (1): 149–153, MR1898206.

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