Editing Kuratowski's theorem

{{Short description|On forbidden subgraphs in planar graphs}}
{{For|the point-set topology theorem|Kuratowski's closure-complement problem}}
[[File:GP92-Kuratowski.svg|thumb|240px|A subdivision of ''K''<sub>3,3</sub> in the [[generalized Petersen graph]] ''G''(9,2), showing that the graph is nonplanar.]]
In [[graph theory]], '''Kuratowski's theorem''' is a mathematical [[forbidden graph characterization]] of [[planar graph]]s, named after [[Kazimierz Kuratowski]].  It states that a finite graph is planar if and only if it does not contain a [[Glossary of graph theory#Subgraphs|subgraph]] that is a [[subdivision (graph theory)|subdivision]] of <math>K_5</math> (the [[complete graph]] on five [[vertex (graph theory)|vertices]]) or of <math>K_{3,3}</math> (a [[complete bipartite graph]] on six vertices, three of which connect to each of the other three, also known as the [[utility graph]]).

==Statement==
A [[planar graph]] is a graph whose vertices can be represented by points in the [[Euclidean plane]], and whose edges can be represented by [[simple curve]]s in the same plane connecting the points representing their endpoints, such that no two curves intersect except at a common endpoint. Planar graphs are often [[graph drawing|drawn]] with straight [[line segment]]s representing their edges, but by [[Fáry's theorem]] this makes no difference to their graph-theoretic characterization.

A [[subdivision (graph theory)|subdivision]] of a graph is a graph formed by subdividing its edges into [[path (graph theory)|paths]] of one or more edges. Kuratowski's theorem states that a finite graph <math>G</math> is planar if it is not possible to subdivide the edges of <math>K_5</math> or <math>K_{3,3}</math>, and then possibly add additional edges and vertices, to form a graph [[graph isomorphism|isomorphic]] to <math>G</math>. Equivalently, a finite graph is planar if and only if it does not contain a subgraph that is [[homeomorphism (graph theory)|homeomorphic]] to <math>K_5</math> or <math>K_{3,3}</math>.

==Kuratowski subgraphs==
{{tesseract_graph_nonplanar_visual_proof.svg}}
If <math>G</math> is a graph that contains a subgraph <math>H</math> that is a subdivision of <math>K_5</math> or <math>K_{3,3}</math>, then <math>H</math> is known as a '''Kuratowski subgraph''' of <math>G</math>.<ref>{{citation
 | last = Tutte | first = W. T. | author-link = W. T. Tutte
 | journal = Proceedings of the London Mathematical Society
 | mr = 0158387
 | pages = 743–767
 | series = Third Series
 | title = How to draw a graph
 | volume = 13
 | year = 1963
 | doi=10.1112/plms/s3-13.1.743}}.</ref>  With this notation, Kuratowski's theorem can be expressed  succinctly: a graph is planar if and only if it does not have a Kuratowski subgraph.

The two graphs <math>K_5</math> and <math>K_{3,3}</math> are nonplanar, as may be shown either by a [[Proof by cases|case analysis]] or an argument involving [[Euler characteristic|Euler's formula]]. Additionally, subdividing a graph cannot turn a nonplanar graph into a planar graph: if a subdivision of a graph <math>G</math> has a planar drawing, the paths of the subdivision form curves that may be used to represent the edges of <math>G</math> itself. Therefore, a graph that contains a Kuratowski subgraph cannot be planar. The more difficult direction in proving Kuratowski's theorem is to show that, if a graph is nonplanar, it must contain a Kuratowski subgraph.

==Algorithmic implications==
A Kuratowski subgraph of a nonplanar graph can be found in [[linear time]], as measured by the size of the input graph.<ref>{{citation
 | last = Williamson | first = S. G.
 | date = September 1984
 | doi = 10.1145/1634.322451
 | issue = 4
 | journal = [[J. ACM]]
 | pages = 681–693
 | title = Depth-first search and Kuratowski subgraphs
 | volume = 31| s2cid = 8348222
 | doi-access = free
 }}.</ref> This allows the correctness of a [[planarity testing]] algorithm to be verified for nonplanar inputs, as it is straightforward to test whether a given subgraph is or is not a Kuratowski subgraph.<ref>{{citation|title=LEDA: A Platform for Combinatorial and Geometric Computing|first1=Kurt|last1=Mehlhorn|author1-link=Kurt Mehlhorn|first2=Stefan|last2=Näher|page=510|url=https://books.google.com/books?id=Q2aXZl3fgvMC&pg=PA510|publisher=Cambridge University Press|year=1999|isbn=9780521563291}}.</ref>
Usually, non-planar graphs contain a large number of Kuratowski-subgraphs. The extraction of these subgraphs is needed, e.g., in [[branch and cut]] algorithms for crossing minimization. It is possible to extract a large number of Kuratowski subgraphs in time dependent on their total size.<ref>{{citation
 | last1 = Chimani| first1 = Markus
 | last2 = Mutzel| first2 = Petra | author2-link = Petra Mutzel
 | last3 = Schmidt| first3 = Jens M.
 | editor1-last = Hong | editor1-first = Seok-Hee | editor1-link = Seok-Hee Hong
 | editor2-last = Nishizeki | editor2-first = Takao | editor2-link = Takao Nishizeki
 | editor3-last = Quan | editor3-first = Wu
 | contribution = Efficient extraction of multiple Kuratowski subdivisions
 | isbn = 978-3-540-77536-2
 | series = [[Lecture Notes in Computer Science]]
 | title =  Graph Drawing: 15th International Symposium, GD 2007, Sydney, Australia, September 24-26, 2007, Revised Papers
 | title-link = International Symposium on Graph Drawing
 | date = 2007
 | doi = 10.1007/978-3-540-77537-9_17 | doi-access = free
 | publisher = Springer
 | pages = 159–170
 | volume = 4875}}</ref>

==History==
[[Kazimierz Kuratowski]] published his theorem in 1930.<ref>{{citation|first=Kazimierz|last=Kuratowski|author-link=Kazimierz Kuratowski|year=1930|url=http://matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf|title=Sur le problème des courbes gauches en topologie|journal=Fund. Math.|volume=15|pages=271–283|doi=10.4064/fm-15-1-271-283 |language=French}}.</ref> The theorem was independently proved by [[Orrin Frink]] and [[Paul Althaus Smith|Paul Smith]], also in 1930,<ref>{{citation
 | last1 = Frink | first1 = Orrin | author-link1 = Orrin Frink
 | last2 = Smith | first2 = Paul A. | author-link2 = Paul Althaus Smith
 | title = Irreducible non-planar graphs
 | journal = Bulletin of the AMS
 | volume = 36
 | pages = 214
 | year = 1930 }}</ref> but their proof was never published.  The special case of [[cubic graph|cubic]] planar graphs (for which the only minimal forbidden subgraph is <math>K_{3,3}</math>) was also independently proved by [[Karl Menger]] in 1930.<ref>{{citation
 | last = Menger | first = Karl | author-link = Karl Menger
 | title = Über plättbare Dreiergraphen und Potenzen nichtplättbarer Graphen
 | journal =  Anzeiger der Akademie der Wissenschaften in Wien
 | volume = 67
 | pages = 85–86
 | year = 1930}}</ref>
Since then, several new proofs of the theorem have been discovered.<ref>{{citation
 | last = Thomassen | first = Carsten | author-link = Carsten Thomassen (mathematician)
 | doi = 10.1002/jgt.3190050304
 | issue = 3
 | journal = Journal of Graph Theory
 | mr = 625064
 | pages = 225–241
 | title = Kuratowski's theorem
 | volume = 5
 | year = 1981}}.</ref>

In the [[Soviet Union]], Kuratowski's theorem was known as either the '''Pontryagin–Kuratowski theorem''' or the '''Kuratowski–Pontryagin theorem''',<ref>{{citation
 | last1 = Burstein | first1 = Michael
 | doi = 10.1016/0095-8956(78)90024-2
 | title = Kuratowski-Pontrjagin theorem on planar graphs
 | journal = Journal of Combinatorial Theory, Series B
 | volume = 24
 | pages = 228–232
 | year = 1978| issue = 2
 | doi-access = 
 }}</ref>
as the theorem was reportedly proved independently by [[Lev Pontryagin]] around 1927.<ref>{{citation
 | last1 = Kennedy | first1 = John W.
 | last2 = Quintas | first2 = Louis V.
 | last3 = Sysło | first3 = Maciej M.
 | doi = 10.1016/0315-0860(85)90045-X
 | title = The theorem on planar graphs
 | journal = Historia Mathematica
 | volume = 12
 | pages = 356–368
 | year = 1985| issue = 4
 | doi-access = free
 }}</ref>
However, as Pontryagin never published his proof, this usage has not spread to other places.<ref>{{citation|title=Graphs & Digraphs|edition=5th|first1=Gary|last1=Chartrand|author1-link=Gary Chartrand|first2=Linda|last2=Lesniak|first3=Ping|last3=Zhang|author3-link=Ping Zhang (graph theorist)|publisher=CRC Press|year=2010|isbn=9781439826270|page=237|url=https://books.google.com/books?id=K6-FvXRlKsQC&pg=PA237}}.</ref>

==Related results==
A closely related result, [[Wagner's theorem]], characterizes the planar graphs by their [[graph minor|minors]] in terms of the same two forbidden graphs <math>K_5</math> and <math>K_{3,3}</math>. Every Kuratowski subgraph is a special case of a minor of the same type, and while the reverse is not true, it is not difficult to find a Kuratowski subgraph (of one type or the other) from one of these two forbidden minors; therefore, these two theorems are equivalent.<ref>{{citation|title=Graph Theory|volume=244|series=Graduate Texts in Mathematics|first1=J. A.|last1=Bondy|author1-link=John Adrian Bondy|first2=U.S.R.|last2=Murty|author2-link=U. S. R. Murty|publisher=Springer|year=2008|isbn=9781846289699|page=269|url=https://books.google.com/books?id=HuDFMwZOwcsC&pg=PA269}}.</ref>

An extension is the [[Robertson–Seymour theorem]].

==See also==
*[[Kelmans–Seymour conjecture]], that 5-connected nonplanar graphs contain a subdivision of <math>K_5</math>

==References==
{{reflist}}

[[Category:Statements about planar graphs]]
[[Category:Theorems in graph theory]]