슈니더의 정리

위키백과, 우리 모두의 백과사전.
(슈나이더의 정리에서 넘어옴)
이동: 둘러보기, 검색

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

정의[편집]

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

u\le uv\qquad\forall uv\in E(G)

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

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

확장[편집]

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

역사[편집]

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

참고 문헌[편집]

  1. Schnyder, W. (1989), "Planar graphs and poset dimension", Order 5: 323–343, doi:10.1007/BF00353652, MR1010382.
  • 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, MR1215230.
  • 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, MR1477654.
  • 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, MR1856785.
  • Ossona de Mendez, P. (2002), "Realization of posets", Journal of Graph Algorithms and Applications 6 (1): 149–153, MR1898206.