슈니더의 정리

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

정의

그래프 $G$에 대하여, 인접 부분 순서 집합(영어: incidence poset) $P(G)$는 집합으로서 분리합집합$P(G)=V(G)\sqcup E(G)$이며, 다음과 같은 부분 순서를 갖는다.

$u\leq uv\qquad \forall uv\in E(G)$

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

슈니더의 정리에 따르면, 유한 그래프 $G$에 대하여 다음 두 조건이 서로 동치이다.

• $G$는 평면 그래프이다.
• $P(G)$의 순서 차원 (교집합이 해당 부분순서가 되는 전순서들의 최소 수)은 3 이하이다.

확장

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

역사

스위스의 수학자 발터 슈니더(독일어: Walter Schnyder)가 1989년에 증명하였다.

참고 문헌

• 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.