그래프 그리기 문서 원본 보기

{{위키데이터 속성 추적}}
[[그래프 이론]]에서 '''그래프 그리기'''({{llang|en|graph drawing}})는 어떤 [[그래프]] 또는 [[다중 그래프]]를 어떤 [[곡면]] 위에, 변이 교차할 수 있게 표시한 것이다.<ref>{{저널 인용|제목=The graph crossing number and its variants: a survey | 저널=The Electronic Journal of Combinatorics | 이름=Marcus | 성=Schaefer | 날짜=2014-05-15 | 권=DS | 쪽=21 | url=http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS21 | 언어=en}}</ref>

== 정의 ==
다음이 주어졌다고 하자.
* 2차원 [[다양체]] <math>\Sigma</math>
* [[다중 그래프]] <math>\Gamma</math>

[[다중 그래프]] <math>\Gamma</math>의, <Math>X</math> 속의 '''그리기'''는 다음 조건들을 모두 만족시키는 [[함수]]
:<math>f\colon\Gamma\to X</math>
이다.
* <math>\Gamma</math>에 [[CW 복합체]] 위상을 주었을 때, <math>f</math>는 [[연속 함수]]이다.
* 임의의 <math>x\in X</math>에 대하여, <math>|f^{-1}(x)| \le 2 </math>이다.
* 변의 교차점은 꼭짓점이 아니다. 즉, <math>\{x\in X\colon |f^{-1}(x)| = 2\} \cap f(\operatorname V(\Gamma)) = \varnothing </math>이다.
* 임의의 두 변의 교차점은 유한 개이다. 즉, 임의의 두 변 <math>e,f\in\operatorname E(\Gamma)</math>에 대하여, <math>\{(s,t) \colon f(s) = f(t),\; s \in t, t\in t\}</math>는 [[유한 집합]]이다. (<math>e\ne f</math>일 필요는 없다. 즉, 변은 스스로와 유한 번 교차할 수 있다.)
* 임의의 교차점 <math>x\in X</math>에 대하여, <math>f\restriction U=\iota_V\circ \tilde f\circ \iota_U</math>가 되는, 다음과 같은 <math>U,V,\iota_U,\iota_V</math>가 존재한다.
*:<math>U\subseteq\Gamma</math>는 [[열린집합]]이다.
*:<math>V\subseteq X</math>는 [[열린집합]]이다.
*:<math>\iota_V\colon \mathbb D^2\to X</math>는 열린 원판에서 <math>V</math>로 가는 [[위상 동형]]이다.
*:<math>\iota_U\colon (-1,1)\sqcup (-1,1)\to U</math>는 두 [[열린구간]]의 [[분리합집합]]에서 <math>U</math>로 가는 [[위상 동형]]이다.
여기서 <math>\tilde f\colon(-1,1)\sqcup (-1,1)\to\mathbb D^2</math>는 다음과 같다.
:<math>(-1,1)\sqcup (-1,1)\cong(-1,1)\times\{\mathsf x,\mathsf y\}</math>라면, <math>f(t,\mathsf x)=(0,t)</math>이며 <math>f(t,\mathsf y)=(t,0)</math>이다.

특히, [[유한 그래프]]의 그리기는 유한 개의 꼭짓점을 갖는다.

[[다중 그래프]] <math>\Gamma</math>의 그리기 <math>f\colon X\to\Gamma</math>의 '''교차수'''는 [[기수 (수학)|기수]]
:<math>|\{x\in X\colon |f^{-1}(x)| = 2\}|</math>
이다. [[다중 그래프]] <math>\Gamma</math>의 '''교차수'''는 평면 <math>\mathbb R^2</math> 속의 그리기의 교차수의 최솟값이며, 이를 <math>\operatorname{cr}(\Gamma)</math>로 표기하자. 보다 일반적으로, 곡면 <math>\Sigma</math> 속의 그리기의 교차수의 최솟값을 <math>\operatorname{cr}_\Sigma(\Gamma)</math>로 표기하자.

교차수가 0인 그래프 그리기를 '''그래프 매장'''(埋藏, {{llang|en|graph embedding}})이라고 한다. [[다중 그래프]] <math>\Gamma</math>의 '''종수'''(種數, {{llang|en|genus}})는 <math>\Gamma</math>가 매장을 갖는 [[연결 공간|연결]] [[콤팩트 공간|콤팩트]] 2차원 [[유향 다양체]] <math>(\mathbb T^2)^{\#g}</math>의 최소 종수 <math>g\in\mathbb N</math>이다.
:<math>\operatorname{genus}(\Gamma) = \min \left\{g\in\mathbb N \colon \operatorname{cr}_{(\mathbb T^2)^{\#g}}(\Gamma) = 0\right\}</math>

== 교차수 부등식 ==
임의의 [[유한 그래프]] <math>\Gamma</math>에 대하여, 다음이 성립한다.
* 만약 <math>|\operatorname E(\Gamma)| > 7|\operatorname V(\Gamma)|</math>라면, <math>29 \operatorname{cr}(\Gamma) |\operatorname V(\Gamma)|^2 \ge |\operatorname E(\Gamma)|^3</math>이다.<ref name="Ackerman"/>
* 만약 <math>|\operatorname E(\Gamma)| > 4 |\operatorname V(\Gamma)|</math>라면, <math>64 \operatorname{cr}(\Gamma) |\operatorname V(\Gamma)|^2 \ge |\operatorname E(\Gamma)|^3</math>이다.

== 예 ==
모든 [[평면 그래프]] <math>\Gamma</math>의 교차수와 종수는 정의에 따라 <math>\operatorname{cr}(\Gamma)=\operatorname{genus}(\Gamma)=0</math>이다.

=== 완전 그래프 ===
[[완전 그래프]]의 교차수는 아직 완전히 알려지지 않있다. 다만, 다음과 같은 부등식이 알려져 있다.
:<math>\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 </math>
이 부등식은 <math>n\le 12</math>에 대하여 등식이라는 것이 알려져 있다. 이 부등식이 <math>n>12</math>인 경우에 대하여 역시 등식이 된다고 추측되지만, 이는 미해결 난제이다.

유한 [[완전 그래프]]의 종수는 다음과 같다. {{OEIS|A933}}
:<math>\operatorname{genus}(K_n) = \begin{cases}
\left\lceil (n-3)(n-4)/12 \right\rceil & n \ge 3\\
0 & n \le 4
\end{cases}</math>
<gallery>
Complete Graph K3.svg|<math>K_3</math>는 [[평면 그래프]]이다. 즉, 그 교차수와 종수는 0이다.
K4 planar.svg|<math>K_4</math>는 [[평면 그래프]]이다. 즉, 그 교차수와 종수는 0이다.
RAC drawings.svg|<math>K_5</math>(왼쪽)의 교차수는 1이며, <math>K_{3,4}</math>(오른쪽)의 교차수는 2이다.
</gallery>

=== 완전 이분 그래프 ===
[[완전 이분 그래프]]의 교차수는 아직 완전히 알려지지 않있다. 다만, 다음과 같은 [[상계 (수학)|상계]]가 알려져 있다.
:<math>\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  </math>
<div class="mw-collapsible mw-collapsed toccolours">
'''[[상계 (수학)|상계]]의 증명''':
<div class="mw-collapsible-content">
<math>K_{m,n}</math>이 주어졌다고 하고, <math>m</math>개의 검은 꼭짓점 및 <math>n</math>개의 흰 꼭짓점으로 [[그래프 색칠]]을 부여하자. 그렇다면, 유클리드 평면에 이들을 다음과 같이 배열한다.
* <math>m</math>개의 검은 꼭짓점들은 <math>x</math>축에 다음과 같이 배열된다.
*:<math> (-\lfloor m/2\rfloor,0),\dotsc, (-2,0), (-1,0),  (1,0), (2,0), \dotsc,(\lceil m/2\rceil,0) </math>
* <math>n</math>개의 흰 꼭짓점들은 <math>y</math>축에 다음과 같이 배열된다.
*:<math> (0,-\lfloor n/2\rfloor),\dotsc, (0,-2), (0,-1),  (0,1), (0,2), \dotsc,(0,\lceil n/2\rceil) </math>
이제, 이를 이으면 평면 속의 <math>K_{m,n}</math>의 그리기가 된다.

이 그리기의 교차수는 다음과 같다. 우선, [[제1 사분면]]에서, 변 <Math>(a,0)-(0,b)</math>와 <math>(a',0)-(0,b')</math>이 교차할 [[필요 충분 조건]]은 <math>(a-a')(b-b')<0</math>인 것이다. 즉, 제1 사분면에서 교차하는 변의 쌍의 수는
:<math>
\begin{aligned}
\left|\left\{(a,a',b,b')\colon 0<a<a' \le \left\lceil\frac m2\right\rceil, 0<b'<b\le \left\lceil \frac n2\right\rceil\right\}\right| & = 
\left(1+2+\dotsb+\left\lceil \frac m2-1\right\rceil\right)
\left(1+2+\dotsb+\left\lceil \frac n2-1\right\rceil\right)\\
&=\frac14
\left\lceil \frac m2-1\right\rceil \left\lceil \frac m2\right\rceil
\left\lceil \frac n2-1\right\rceil \left\lceil \frac n2\right\rceil
\end{aligned}
</math>
이다. 나머지 [[사분면]]들도 마찬가지로 계산된다. 즉, 이 그래프 그리기의 교차점의 수는 다음과 같다.
:<math>\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}
</math>
</div></div>
또한, 이 부등식이 등식이 될 다음과 같은 [[충분 조건]]이 알려져 있다.
* <math>\min\{m,n\} \le 6</math>일 때<ref>{{저널 인용
 | last = Kleitman | first = Daniel J.
 | journal = Journal of Combinatorial Theory
 | mr = 0280403
 | pages = 315–323
 | title = The crossing number of ''K''<sub>5,''n''</sub>
 | volume = 9
 | year = 1970
 | doi=10.1016/s0021-9800(70)80087-4 |언어=en}}</ref>
* <math>7 = \min\{m,n\} \le \max\{ m,n \} \le 9 </math><ref>{{저널 인용
 | last = Woodall | first = D. R.
 | doi = 10.1002/jgt.3190170602
 | issue = 6
 | journal = Journal of Graph Theory
 | mr = 1244681
 | pages = 657–671
 | title = Cyclic-order graphs and Zarankiewicz's crossing-number conjecture
 | volume = 17
 | 날짜 = 1993-12 | issn=0364-9024 | 언어=en}}</ref>
'''자란키에비치 추측'''(Zarankiewicz推測, {{llang|en|Zarankiewicz conjecture}})에 따르면, 이 부등식이 항상 등식이 된다고 추측되지만, 이는 미해결 난제이다.

유한 [[완전 이분 그래프]]의 종수는 다음과 같다.
:<math>\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}
 </math>

<gallery>
GraphMinorExampleA.png|<math>K_{1,4}</math>의 교차수는 0이다.
Circle graph C4.svg|<math>K_{2,2}</math>의 교차수는 0이다.
Graph homeomorphism example 1.svg|<math>K_{2,3}</math>의 교차수는 0이다.
K33 one crossing.svg|<math>K_{3,3}</math>의 교차수는 1이다.
Zarankiewicz K4,7.svg|<math>K_{4,7}</math>의 교차수는 18이다.
</gallery>

=== 일반화 페테르센 그래프 ===
[[각기둥]] 그래프 <math>\operatorname{GPG}(n,1)</math>은 [[평면 그래프]]이므로, 교차수와 종수가 0이다. <math>\operatorname{GPG}(6,2)</math> 역시 [[평면 그래프]]이다.

[[페테르센 그래프]] <math>\operatorname{GPG}(5,2)</math>의 교차수는 2이다.
[[일반화 페테르센 그래프]] <math>\operatorname{GPG}(8,3)</math>의 교차수는 4이며, 그 종수는 1이다. [[데자르그 그래프]] <math>\operatorname{GPG}(10,3)</math>의 교차수는 6이다. [[나우루 그래프]] <math>\operatorname{GPG}(12,5)</math>의 교차수는 8이다. 특히, 이 두 그래프 둘 다 [[평면 그래프]]가 아니다.

<gallery>
Octagonal prismatic graph.svg|팔각 기둥 그래프 <math>\operatorname{GPG}(8,1)</math>은 [[평면 그래프]]이므로, 그 교차수와 종수는 0이다.
Petersen graph, two crossings.svg|[[페테르센 그래프]] <math>\operatorname{GPG}(5,2)</math>의 교차수는 2이다.
Nauru 1-planar 8-crossing.svg|[[나우루 그래프]] <math>\operatorname{GPG}(12,5)</math>의 교차수는 8이다.
Möbius–Kantor_torus.svg|<math>\operatorname{GPG}(8,3)</math>의, [[원환면]] <math>\mathbb T^2</math> 속의 매장. 따라서, <math>\operatorname{GPG}(8,3)</math>의 종수는 1이다.
</gallery>

== 역사 ==
하나니-텃 정리는 하임 하나니({{llang|he|חַיִּים חַנַנִי}}, 舊名 {{llang|pl|Chaim Chojnacki|하임 호이나츠키}}, 1912~1991)가 1934년에 증명하였으나, 하나니는 이를 논문에 매우 간접적으로 언급하였다.<ref>{{저널 인용
 | last = Chojnacki | first = Chaim
 | 권=23
 | 호 = 1
 | journal = Fundamenta Mathematicae
 | pages = 135–142
 | title = Über wesentlich unplättbare Kurven im dreidimensionalen Raume
 | url = http://pldml.icm.edu.pl/pldml/element/bwmeta1.element.bwnjournal-article-fmv23i1p13bwm
 | 날짜 = 1934 | issn=0016-2736 | zbl=0009.41104 | jfm=60.0528.02 | 언어=de}}</ref> 1970년에 [[윌리엄 토머스 텃]]이 이 정리를 (직접적으로) 다시 언급하였다.<ref>{{저널 인용
 | last = Tutte | first = William Thomas | authorlink = 윌리엄 토머스 텃
 | journal = Journal of Combinatorial Theory
 | mr = 0262110
 | pages = 45–53
 | title = Toward a theory of crossing numbers
 | volume = 8
 | year = 1970
 | doi=10.1016/s0021-9800(70)80007-2 | zbl=0187.20803 | 언어=en}}</ref>

[[파일:Agyagfogadó garat a szentesi téglagyárban.JPG|섬네일|헝가리의 한 벽돌 공장의 철로]]
[[파일:ZarankiewiczKazimierz Moscow1935.tif|섬네일|카지미에시 자란키에비치({{llang|pl|Kazimierz Zarankiewicz}}). 1935년 사진]]
[[파일:1981-02-27 uczestnicy Urbanik002.jpg|섬네일|right|카지미에시 우르바니크({{llang|pl|Kazimierz Urbanik}}). 1981년 사진]]
[[완전 이분 그래프]]의 교차수를 계산하는 문제는 [[투란 팔]]이 1944년에 최초로 제시하였다.<ref>{{저널 인용|제목=The early history of the brick factory problem|저널=The Mathematical Intelligencer|이름=Lowell|성=Beineke|이름2=Robin|성2=Wilson|doi= 10.1007/s00283-009-9120-4|날짜=2010-06|권=32|호=2|쪽=41–48|언어=en}}</ref><ref>{{서적 인용|장=Turán’s brick factory problem: the status of the conjectures of Zarankiewicz and Hill|doi= 10.1007/978-3-319-31940-7_13|이름=László A.|성=Székely|날짜=2016|제목=
Graph theory: favorite conjectures and open problems 1|총서=Problem Books in Mathematics|issn=0941-3502|isbn=978-3-319-31938-4|쪽=211–230|editor1-first= Ralucca |editor1-last=Gera|editor2-first= Stephen|editor2-last= Hedetniemi|editor3-first= Craig|editor3-last= Larson |언어=en}}</ref> 이에 대하여 투란은 다음과 같이 적었다.
{{인용문2|
1944년 7월에는 [<nowiki></nowiki>[[제2차 세계 대전 기간의 헝가리|추축국]]의 [[유대인]]으로서] [[부다페스트]] 안에서는 강제 추방의 위험이 팽배하였으며, [[부다페스트]] 밖에서는 현재 진행형이었다. 우리는 [[부다페스트]] 근교의 벽돌 공장에서 노역(奴役)을 당하였다. 벽돌 가마들은 저장고들과 철로로 연결되었다. 벽돌은 작은 트롤리에 실려 저장고로 이동되었다. […] 문제는 철로의 교차점에서였다. 트롤리들은 교차점에서 탈선하기 일쑤였으며, 이 경우 벽돌들이 모두 쏟아지게 되었다. […] 갑자기 나는 불쑥 다음과 같은 아이디어를 떠올렸다. ‘교차점의 수를 최소화하면, 이러한 문제는 최소화될 것이다. 그런데 교차점의 수의 최솟값은 얼마일까?’ […] <math>m</math>개의 가마와 <math>n</math>개의 저장고에 대한 일반적 문제는 매우 어려운 것 같았으며, 나는 가족의 생사가 불명한 상황에서 이 문제를 접어 두었다. (훗날 나는 1952년에 [[폴란드]]를 방문하여 자란키에비치를 만났으며, 그에게 “벽돌 공장” 문제를 언급하였다. […])
<br>
{{lang|en|In July 1944 the danger of deportation was real in Budapest, and a reality outside Budapest. We worked near Budapest, in a brick factory. There were some kilns where the bricks were made and some open storage yards where the bricks were stored. All the kilns were connected by rail with all the storage yards. The bricks were carried on small wheeled trucks to the storage yeards [''sic'']. […] [T]he trouble was only at the crossings. The trucks generally jumped the rails there, and the bricks fell out of them; […] ''nolens–volens'' the idea occurred to me that this loss of time could have been minimized if the number of crossings of the rails had been minimized. But what is the minimum number of crossings? […] [T]he exact solution of the general problem with ''m'' kilns and ''n'' storage yards seemed to be very difficult and again I postponed my study of it to times when my fears for my family would end. (But the problem occurred to me again not earlier than 1952, at my first visit to Poland where I met Zarankiewicz. I mentioned to him my “brick-factory”-problem […])}}
|<ref>{{저널 인용|성=Turán|이름=Pál|저자링크=투란 팔|날짜=1977|제목=A note of welcome|url=https://archive.org/details/sim_journal-of-graph-theory_spring-1977_1_1/page/n12|저널=Journal of Graph Theory|권=1|쪽=7–9|doi=10.1002/jgt.3190010105|언어=en}}</ref>{{rp|8–8}}
}}
투란에게서 이 문제를 들은 카지미에시 자란키에비치({{llang|pl|Kazimierz Zarankiewicz}}, 1902~1959)<ref>{{저널 인용|성=Zarankiewicz|이름=Kazimierz|제목=On a problem of P. Turan concerning graphs|저널=Fundamenta Mathematicae|권=41|쪽=137–145|날짜=1954|issn=0016-2736|url=http://pldml.icm.edu.pl/pldml/element/bwmeta1.element.bwnjournal-article-fmv41i1p137bwm | zbl=0055.41605 | mr=63641 | 언어=en}}</ref>와 카지미에시 우르바니크({{llang|pl|Kazimierz Urbanik}}, 1930~2005)<ref>{{저널 인용
 | last = Urbanik | first = Kazimierz
 | journal = Colloquium Mathematicum
 | pages = 200–201
 | title = Solution du problème posé par P. Turán
 | volume = 3 | issn=0010-1354
 | 날짜 = 1953-01-02 | url=http://matwbn.icm.edu.pl/ksiazki/cm/cm3/cm3126.pdf#page=14 | 언어=fr}}</ref>는 둘 다 각각 1950년대 초에 이 문제를 “해결”하는 논문을 출판하였으나, 이들의 증명은 훗날 오류가 있어, 오직 교차수의 [[상계 (수학)|상계]]만을 증명한다는 것이 밝혀졌다.<ref>{{서적 인용|장=The decline and fall of Zarankiewicz’s theorem|이름=Richard Kenneth | 성=Guy | 날짜=1969 | isbn=978-012324260-0| |제목=Proof techniques in graph theory. Proceedings of the Second Ann Arbor Graph Theory Conference 1968 |  출판사=Academic Press | zbl=0192.60601 | editor1-last=Harary|editor1-first=Frank| 쪽=63–69 | 언어=en}}</ref>

교차수 부등식은 1980년대 초에  어이터이 미클로시({{llang|hu|Ajtai Miklós}}, 1946~) · 바츨라프 흐바탈({{llang|cs|Václav Chvátal}}, 1946~) · 몬로 몬티 뉴본({{llang|en|Monroe Monty Newborn}}, 1938~) · [[세메레디 엔드레]]<ref>{{서적 인용
 | last1 = Ajtai | first1 = Miklós
 | last2 = Chvátal | first2 = Václav
 | last3 = Newborn | first3 = Monroe Monty
 | last4 = Szemerédi | first4 = Endre | author4-link = 세메레디 엔드레
 | 장 = Crossing-free subgraphs
 | mr = 806962
 | 쪽 = 9–12
 | 출판사 = North-Holland
 | 총서 = Annals of Discrete Mathematics | 권=12
 | 제목 = Theory and practice of combinatorics. A collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday
 | doi=10.1016/S0304-0208(08)73484-4
 |editor1-first= Alexander |editor1-last=Rosa
 |editor2-first = Gert |editor2-last=Sabidussi
 |editor3-first= Jean |editor3-last=Turgeon
 | 날짜 = 1982
 | isbn=978-0-444-86318-8
 | zbl=0502.05021
 | 언어=en}}
</ref>와 프랭크 톰슨 레이턴({{llang|en|Frank Thomson Leighton}}, 1956~)<ref>{{서적 인용|성=Leighton|이름=Frank Thomson|날짜=1983|제목=Complexity issues in VLSI. Optimal layouts for the shuffle-exchange graph and other networks |총서=Foundations of Computing Series|출판사=Massachusetts Institute of Technology Press|url=https://mitpress.mit.edu/books/complexity-issues-vlsi|isbn=978-0-262-62178-6|언어=en}}</ref>이 최초로 증명하였으며, 이후 후대 수학자들이 그 상수를 개선하였다.<ref name="Ackerman">{{저널 인용|성=Ackerman|이름=Eyal|날짜=2013|제목=On topological graphs with at most four crossings per edge |arxiv=1509.01932 | bibcode=2015arXiv150901932A | 언어=en}}</ref>

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Graph imbedding}}
* {{eom|title=Zarankiewicz crossing number conjecture}}
* {{매스월드|id=GraphEmbedding|title=Graph embedding}}
* {{매스월드|id=GraphCrossingNumber|title=Graph crossing number}}
* {{매스월드|id=ToroidalCrossingNumber|title=Toroidal crossing number}}
* {{매스월드|id=ProjectivePlaneCrossingNumber|title=Projective plane crossing number}}
* {{매스월드|id=ZarankiewiczsConjecture|title=Zarankiewicz’s conjecture}}
* {{매스월드|id=StraightLineDrawing|title=Straight line drawing}}
* {{매스월드|id=RectilinearCrossingNumber|title=Rectilinear crossing number}}
* {{매스월드|id=IntegralEmbedding|title=Integral embedding}}
* {{매스월드|id=Unit-DistanceDrawing|title=Unit-distance drawing}}
* {{매스월드|id=GraphGenus|title=Graph genus}}
* {{웹 인용|url=https://mappingignorance.org/2013/08/13/the-fascinating-history-of-the-brick-factory-problem/ | 제목=
The fascinating history of the brick factory problem|웹사이트=Mapping Ignorance|이름=David|성=Orden|날짜=2013-08-13|issn=2529-8992|출판사=Euskal Herriko Unibertsitatea|언어=en}}

{{그래프 표현}}

[[분류:그래프 그리기| ]]
[[분류:그래프 이론]]