그래프 그리기

그래프 이론에서 **그래프 그리기**(graph drawing)는 어떤 그래프 또는 다중 그래프를 어떤 곡면 위에, 변이 교차할 수 있게 표시한 것이다.언어=en
# 정의
다음이 주어졌다고 하자. * 2차원 다양체 \Sigma * 다중 그래프 \Gamma 다중 그래프 \Gamma의, X 속의 **그리기**는 다음 조건들을 모두 만족시키는 함수 :f\colon\Gamma\to X 이다. * \Gamma에 CW 복합체 위상을 주었을 때, f는 연속 함수이다. * 임의의 x\in X에 대하여, |f^{-1}(x)| \le 2 이다. * 변의 교차점은 꼭짓점이 아니다. 즉, \\{x\in X\colon |f^{-1}(x)| = 2\\} \cap f(\operatorname V(\Gamma)) = \varnothing 이다. * 임의의 두 변의 교차점은 유한 개이다. 즉, 임의의 두 변 e,f\in\operatorname E(\Gamma)에 대하여, \\{(s,t) \colon f(s) = f(t),\; s \in t, t\in t\\}는 유한 집합이다. (e\ne f일 필요는 없다. 즉, 변은 스스로와 유한 번 교차할 수 있다.) * 임의의 교차점 x\in X에 대하여, f\restriction U=\iota_V\circ \tilde f\circ \iota_U가 되는, 다음과 같은 U,V,\iota_U,\iota_V가 존재한다. *:U\subseteq\Gamma는 열린집합이다. *:V\subseteq X는 열린집합이다. *:\iota_V\colon \mathbb D^2\to X는 열린 원판에서 V로 가는 위상 동형이다. *:\iota_U\colon (-1,1)\sqcup (-1,1)\to U는 두 열린구간의 분리합집합에서 U로 가는 위상 동형이다. 여기서 \tilde f\colon(-1,1)\sqcup (-1,1)\to\mathbb D^2는 다음과 같다. :(-1,1)\sqcup (-1,1)\cong(-1,1)\times\\{\mathsf x,\mathsf y\\}라면, f(t,\mathsf x)=(0,t)이며 f(t,\mathsf y)=(t,0)이다. 특히, 유한 그래프의 그리기는 유한 개의 꼭짓점을 갖는다. 다중 그래프 \Gamma의 그리기 f\colon X\to\Gamma의 **교차수**는 기수 :|\\{x\in X\colon |f^{-1}(x)| = 2\\}| 이다. 다중 그래프 \Gamma의 **교차수**는 평면 \mathbb R^2 속의 그리기의 교차수의 최솟값이며, 이를 \operatorname{cr}(\Gamma)로 표기하자. 보다 일반적으로, 곡면 \Sigma 속의 그리기의 교차수의 최솟값을 \operatorname{cr}_\Sigma(\Gamma)로 표기하자. 교차수가 0인 그래프 그리기를 **그래프 매장**(埋藏, graph embedding)이라고 한다. 다중 그래프 \Gamma의 **종수**(種數, genus)는 \Gamma가 매장을 갖는 연결 콤팩트 2차원 유향 다양체 (\mathbb T^2)^{\\#g}의 최소 종수 g\in\mathbb N이다. :\operatorname{genus}(\Gamma) = \min \left\\{g\in\mathbb N \colon \operatorname{cr}_{(\mathbb T^2)^{\\#g(\Gamma) = 0\right\\}
# 교차수 부등식
임의의 유한 그래프 \Gamma에 대하여, 다음이 성립한다. * 만약 |\operatorname E(\Gamma)| > 7|\operatorname V(\Gamma)|라면, 29 \operatorname{cr}(\Gamma) |\operatorname V(\Gamma)|^2 \ge |\operatorname E(\Gamma)|^3이다. * 만약 |\operatorname E(\Gamma)| > 4 |\operatorname V(\Gamma)|라면, 64 \operatorname{cr}(\Gamma) |\operatorname V(\Gamma)|^2 \ge |\operatorname E(\Gamma)|^3이다.
# 예
모든 평면 그래프 \Gamma의 교차수와 종수는 정의에 따라 \operatorname{cr}(\Gamma)=\operatorname{genus}(\Gamma)=0이다.
## 완전 그래프
완전 그래프의 교차수는 아직 완전히 알려지지 않있다. 다만, 다음과 같은 부등식이 알려져 있다. :\operatorname{cr}(K_n) \le \frac14 \left\lfloor \frac n2\right\rfloor \left\lfloor \frac{n-1}2\right\rfloor \left\lfloor \frac {n-2}2\right\rfloor \left\lfloor \frac {n-3}2\right\rfloor 이 부등식은 n\le 12에 대하여 등식이라는 것이 알려져 있다. 이 부등식이 n>12인 경우에 대하여 역시 등식이 된다고 추측되지만, 이는 미해결 난제이다. 유한 완전 그래프의 종수는 다음과 같다. A933 :\operatorname{genus}(K_n) = \begin{cases} \left\lceil (n-3)(n-4)/12 \right\rceil & n \ge 3\\\ 0 & n \le 4 \end{cases} Complete Graph 평면 그래프이다. 즉, 그 교차수와 종수는 0이다. K4 평면 그래프이다. 즉, 그 교차수와 종수는 0이다. RAC 교차수는 1이며, K_{3,4}(오른쪽)의 교차수는 2이다.
## 완전 이분 그래프
완전 이분 그래프의 교차수는 아직 완전히 알려지지 않있다. 다만, 다음과 같은 상계가 알려져 있다. :\operatorname{cr}(K_{m,n}) \le \left\lfloor \frac m2\right\rfloor \left\lfloor \frac {m-1}2\right\rfloor\left\lfloor \frac n2\right\rfloor \left\lfloor \frac{n-1}2\right\rfloor

**상계의 증명**:

K_{m,n}이 주어졌다고 하고, m개의 검은 꼭짓점 및 n개의 흰 꼭짓점으로 그래프 색칠을 부여하자. 그렇다면, 유클리드 평면에 이들을 다음과 같이 배열한다. * m개의 검은 꼭짓점들은 x축에 다음과 같이 배열된다. *: (-\lfloor m/2\rfloor,0),\dotsc, (-2,0), (-1,0), (1,0), (2,0), \dotsc,(\lceil m/2\rceil,0) * n개의 흰 꼭짓점들은 y축에 다음과 같이 배열된다. *: (0,-\lfloor n/2\rfloor),\dotsc, (0,-2), (0,-1), (0,1), (0,2), \dotsc,(0,\lceil n/2\rceil) 이제, 이를 이으면 평면 속의 K_{m,n}의 그리기가 된다. 이 그리기의 교차수는 다음과 같다. 우선, 제1 사분면에서, 변 (a,0)-(0,b)와 (a',0)-(0,b')이 교차할 필요 충분 조건은 (a-a')(b-b')<0인 것이다. 즉, 제1 사분면에서 교차하는 변의 쌍의 수는 : \begin{aligned} \left|\left\\{(a,a',b,b')\colon 0 이다. 나머지 사분면들도 마찬가지로 계산된다. 즉, 이 그래프 그리기의 교차점의 수는 다음과 같다. :\begin{aligned} \operatorname{cr}(K_{m,n}) &\le \frac14 \left( \left\lceil \frac m2-1\right\rceil \left\lceil \frac m2\right\rceil \+ \left\lfloor \frac m2-1\right\rfloor \left\lfloor \frac m2\right\rfloor \right) \left( \left\lceil \frac n2-1\right\rceil \left\lceil \frac n2\right\rceil \+ \left\lfloor \frac n2-1\right\rfloor \left\lfloor \frac n2\right\rfloor \right) \\\ &=\left\lfloor \frac m2\right\rfloor \left\lfloor \frac {m-1}2\right\rfloor\left\lfloor \frac n2\right\rfloor \left\lfloor \frac{n-1}2\right\rfloor \end{aligned}

또한, 이 부등식이 등식이 될 다음과 같은 충분 조건이 알려져 있다. * \min\\{m,n\\} \le 6일 때언어=en * 7 = \min\\{m,n\\} \le \max\\{ m,n \\} \le 9 언어=en **자란키에비치 추측**(Zarankiewicz推測, Zarankiewicz conjecture)에 따르면, 이 부등식이 항상 등식이 된다고 추측되지만, 이는 미해결 난제이다. 유한 완전 이분 그래프의 종수는 다음과 같다. :\operatorname{genus}(K_{m,n}) = \begin{cases}\left\lceil (m-2)(n-2)/4 \right\rceil & \min\\{m,n\\} \ge2 \\\ 0 & \min\\{m,n\\} \le 2 \end{cases} GraphMinorExampleA.png|K_{1,4}의 교차수는 0이다. Circle graph C4.svg|K_{2,2}의 교차수는 0이다. Graph homeomorphism example 1.svg|K_{2,3}의 교차수는 0이다. K33 one crossing.svg|K_{3,3}의 교차수는 1이다. Zarankiewicz K4,7.svg|K_{4,7}의 교차수는 18이다.
## 일반화 페테르센 그래프
각기둥 그래프 \operatorname{GPG}(n,1)은 평면 그래프이므로, 교차수와 종수가 0이다. \operatorname{GPG}(6,2) 역시 평면 그래프이다. 페테르센 그래프 \operatorname{GPG}(5,2)의 교차수는 2이다. 일반화 페테르센 그래프 \operatorname{GPG}(8,3)의 교차수는 4이며, 그 종수는 1이다. 데자르그 그래프 \operatorname{GPG}(10,3)의 교차수는 6이다. 나우루 그래프 \operatorname{GPG}(12,5)의 교차수는 8이다. 특히, 이 두 그래프 둘 다 평면 그래프가 아니다. Octagonal prismatic 기둥 그래프 \operatorname{GPG}(8,1)은 평면 그래프이므로, 그 교차수와 종수는 0이다. Petersen graph, two 그래프 \operatorname{GPG}(5,2)의 교차수는 2이다. Nauru 1-planar 그래프 \operatorname{GPG}(12,5)의 교차수는 8이다. Möbius–Kantor_torus.svg|\operatorname{GPG}(8,3)의, 원환면 \mathbb T^2 속의 매장. 따라서, \operatorname{GPG}(8,3)의 종수는 1이다.
# 역사
하나니-텃 정리는 하임 하나니(חַיִּים חַנַנִי, 舊名 하임 호이나츠키, 1912~1991)가 1934년에 증명하였으나, 하나니는 이를 논문에 매우 간접적으로 언급하였다.언어=de 1970년에 윌리엄 토머스 텃이 이 정리를 (직접적으로) 다시 언급하였다.언어=en 헝가리의 한 벽돌 공장의 철로 Kazimierz Zarankiewicz). 1935년 사진 Kazimierz Urbanik). 1981년 사진 완전 이분 그래프의 교차수를 계산하는 문제는 투란 팔이 1944년에 최초로 제시하였다.언어=en언어=en 이에 대하여 투란은 다음과 같이 적었다. 8–8 투란에게서 이 문제를 들은 카지미에시 자란키에비치(Kazimierz Zarankiewicz, 1902~1959)언어=en와 카지미에시 우르바니크(Kazimierz Urbanik, 1930~2005)언어=fr는 둘 다 각각 1950년대 초에 이 문제를 “해결”하는 논문을 출판하였으나, 이들의 증명은 훗날 오류가 있어, 오직 교차수의 상계만을 증명한다는 것이 밝혀졌다.언어=en 교차수 부등식은 1980년대 초에 어이터이 미클로시(Ajtai Miklós, 1946~) · 바츨라프 흐바탈(Václav Chvátal, 1946~) · 몬로 몬티 뉴본(Monroe Monty Newborn, 1938~) · 세메레디 엔드레언어=en 와 프랭크 톰슨 레이턴(Frank Thomson Leighton, 1956~)언어=en이 최초로 증명하였으며, 이후 후대 수학자들이 그 상수를 개선하였다.언어=en