Editing Kuratowski's theorem (section)

==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>