372:
27:
847:. 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.
687:
algorithm to be verified for nonplanar inputs, as it is straightforward to test whether a given subgraph is or is not a
Kuratowski subgraph. Usually, non-planar graphs contain a large number of Kuratowski-subgraphs. The extraction of these subgraphs is needed, e.g., in
670:
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.
845:
746:
620:
513:
361:
273:
142:
891:
812:
587:
480:
328:
240:
101:
668:
648:
557:
533:
453:
433:
297:
213:
172:
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
559:. 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.
692:
algorithms for crossing minimization. It is possible to extract a large number of
Kuratowski subgraphs in time dependent on their total size.
20:
1030:
1054:
1325:
1298:
1264:
1154:
1036:
1001:
630:. Additionally, subdividing a graph cannot turn a nonplanar graph into a planar graph: if a subdivision of a graph
57:
863:
1032:
Graph
Drawing: 15th International Symposium, GD 2007, Sydney, Australia, September 24-26, 2007, Revised Papers
851:
69:
409:
300:
771:
around 1927. However, as
Pontryagin never published his proof, this usage has not spread to other places.
650:
has a planar drawing, the paths of the subdivision form curves that may be used to represent the edges of
1250:
188:
73:
38:
145:
1320:
299:. Equivalently, a finite graph is planar if and only if it does not contain a subgraph that is
1288:
1254:
1218:
Kennedy, John W.; Quintas, Louis V.; Sysło, Maciej M. (1985), "The theorem on planar graphs",
991:
817:
718:
592:
485:
333:
245:
114:
108:
1178:
1069:
934:
869:
790:
700:
627:
565:
458:
306:
218:
79:
65:
1021:; Schmidt, Jens M. (2007), "Efficient extraction of multiple Kuratowski subdivisions", in
181:
8:
780:
391:
375:
371:
192:
1110:
1073:
969:
708:
653:
633:
542:
518:
438:
418:
282:
198:
148:
on six vertices, three of which connect to each of the other three, also known as the
1294:
1280:
1260:
1232:
1205:
1050:
997:
684:
276:
1227:
1201:
1166:
1088:
1040:
973:
959:
948:
Williamson, S. G. (September 1984), "Depth-first search and
Kuratowski subgraphs",
922:
1174:
1045:
1026:
930:
379:
165:
68:. It states that a finite graph is planar if and only if it does not contain a
1284:
1246:
926:
768:
689:
683:, as measured by the size of the input graph. This allows the correctness of a
623:
104:
1314:
1135:(1930), "Über plättbare Dreiergraphen und Potenzen nichtplättbarer Graphen",
1022:
987:
752:
in 1930. Since then, several new proofs of the theorem have been discovered.
173:
149:
1192:
Burstein, Michael (1978), "Kuratowski-Pontrjagin theorem on planar graphs",
1092:
1170:
1018:
756:
383:
177:
169:
161:
61:
49:
711:, also in 1930, but their proof was never published. The special case of
1132:
1106:
910:
784:
749:
712:
704:
680:
964:
1293:, Graduate Texts in Mathematics, vol. 244, Springer, p. 269,
703:
published his theorem in 1930. The theorem was independently proved by
275:, and then possibly add additional edges and vertices, to form a graph
195:
of one or more edges. Kuratowski's theorem states that a finite graph
184:
this makes no difference to their graph-theoretic characterization.
26:
715:
planar graphs (for which the only minimal forbidden subgraph is
950:
164:
is a graph whose vertices can be represented by points in the
866:, that 5-connected nonplanar graphs contain a subdivision of
679:
A Kuratowski subgraph of a nonplanar graph can be found in
191:
of a graph is a graph formed by subdividing its edges into
993:
215:
is planar if it is not possible to subdivide the edges of
767:, as the theorem was reportedly proved independently by
1245:
872:
820:
793:
721:
656:
636:
595:
568:
545:
521:
488:
461:
441:
421:
336:
309:
285:
248:
221:
201:
117:
82:
1016:
1217:
1074:"Sur le problème des courbes gauches en topologie"
885:
839:
806:
740:
662:
642:
614:
581:
551:
527:
507:
474:
447:
427:
355:
322:
291:
267:
234:
207:
136:
95:
1312:
1137:Anzeiger der Akademie der Wissenschaften in Wien
759:, Kuratowski's theorem was known as either the
1039:, vol. 4875, Springer, pp. 159–170,
915:Proceedings of the London Mathematical Society
986:
996:, Cambridge University Press, p. 510,
783:, characterizes the planar graphs by their
674:
622:are nonplanar, as may be shown either by a
44:(9,2), showing that the graph is nonplanar.
1279:
1105:
1068:
947:
787:in terms of the same two forbidden graphs
1231:
1194:Journal of Combinatorial Theory, Series B
1153:
1113:(1930), "Irreducible non-planar graphs",
1044:
963:
1259:(5th ed.), CRC Press, p. 237,
1191:
370:
168:, and whose edges can be represented by
25:
19:For the point-set topology theorem, see
366:
21:Kuratowski's closure-complement problem
16:On forbidden subgraphs in planar graphs
1313:
1131:
909:
435:is a graph that contains a subgraph
748:) was also independently proved by
13:
774:
14:
1337:
1037:Lecture Notes in Computer Science
180:representing their edges, but by
1157:(1981), "Kuratowski's theorem",
58:forbidden graph characterization
1273:
1239:
1211:
913:(1963), "How to draw a graph",
1185:
1147:
1125:
1099:
1062:
1010:
980:
941:
903:
1:
896:
765:Kuratowski–Pontryagin theorem
761:Pontryagin–Kuratowski theorem
1233:10.1016/0315-0860(85)90045-X
1206:10.1016/0095-8956(78)90024-2
1046:10.1007/978-3-540-77537-9_17
155:
7:
857:
10:
1342:
864:Kelmans–Seymour conjecture
779:A closely related result,
695:
39:generalized Petersen graph
18:
852:Robertson–Seymour theorem
626:or an argument involving
455:that is a subdivision of
1326:Theorems in graph theory
990:; Näher, Stefan (1999),
927:10.1112/plms/s3-13.1.743
675:Algorithmic implications
146:complete bipartite graph
1159:Journal of Graph Theory
1093:10.4064/fm-15-1-271-283
840:{\displaystyle K_{3,3}}
741:{\displaystyle K_{3,3}}
615:{\displaystyle K_{3,3}}
508:{\displaystyle K_{3,3}}
356:{\displaystyle K_{3,3}}
268:{\displaystyle K_{3,3}}
137:{\displaystyle K_{3,3}}
1171:10.1002/jgt.3190050304
887:
841:
808:
742:
664:
644:
616:
583:
553:
529:
509:
476:
449:
429:
412:
357:
324:
293:
269:
236:
209:
138:
97:
45:
1256:Graphs & Digraphs
1070:Kuratowski, Kazimierz
888:
886:{\displaystyle K_{5}}
842:
809:
807:{\displaystyle K_{5}}
743:
665:
645:
617:
584:
582:{\displaystyle K_{5}}
554:
530:
510:
477:
475:{\displaystyle K_{5}}
450:
430:
374:
358:
325:
323:{\displaystyle K_{5}}
294:
270:
237:
235:{\displaystyle K_{5}}
210:
139:
98:
96:{\displaystyle K_{5}}
29:
1220:Historia Mathematica
870:
850:An extension is the
818:
791:
719:
701:Kazimierz Kuratowski
654:
634:
593:
566:
543:
519:
486:
459:
439:
419:
367:Kuratowski subgraphs
334:
307:
283:
246:
219:
199:
115:
80:
66:Kazimierz Kuratowski
54:Kuratowski's theorem
1115:Bulletin of the AMS
1029:; Quan, Wu (eds.),
965:10.1145/1634.322451
537:Kuratowski subgraph
394:and finding either
376:Proof without words
1249:; Lesniak, Linda;
1155:Thomassen, Carsten
883:
837:
804:
738:
660:
640:
612:
579:
549:
525:
505:
472:
445:
425:
413:
353:
320:
289:
265:
232:
205:
134:
93:
56:is a mathematical
46:
1056:978-3-540-77536-2
1017:Chimani, Markus;
685:planarity testing
663:{\displaystyle G}
643:{\displaystyle G}
552:{\displaystyle G}
528:{\displaystyle H}
448:{\displaystyle H}
428:{\displaystyle G}
392:Wagner's theorems
292:{\displaystyle G}
208:{\displaystyle G}
30:A subdivision of
1333:
1305:
1303:
1277:
1271:
1269:
1243:
1237:
1236:
1235:
1215:
1209:
1208:
1189:
1183:
1181:
1151:
1145:
1144:
1129:
1123:
1122:
1103:
1097:
1095:
1078:
1066:
1060:
1059:
1048:
1027:Nishizeki, Takao
1014:
1008:
1006:
984:
978:
976:
967:
945:
939:
937:
917:, Third Series,
907:
892:
890:
889:
884:
882:
881:
846:
844:
843:
838:
836:
835:
813:
811:
810:
805:
803:
802:
781:Wagner's theorem
747:
745:
744:
739:
737:
736:
669:
667:
666:
661:
649:
647:
646:
641:
621:
619:
618:
613:
611:
610:
588:
586:
585:
580:
578:
577:
558:
556:
555:
550:
534:
532:
531:
526:
514:
512:
511:
506:
504:
503:
481:
479:
478:
473:
471:
470:
454:
452:
451:
446:
434:
432:
431:
426:
362:
360:
359:
354:
352:
351:
329:
327:
326:
321:
319:
318:
298:
296:
295:
290:
274:
272:
271:
266:
264:
263:
241:
239:
238:
233:
231:
230:
214:
212:
211:
206:
143:
141:
140:
135:
133:
132:
102:
100:
99:
94:
92:
91:
1341:
1340:
1336:
1335:
1334:
1332:
1331:
1330:
1311:
1310:
1309:
1308:
1301:
1278:
1274:
1267:
1247:Chartrand, Gary
1244:
1240:
1216:
1212:
1190:
1186:
1152:
1148:
1130:
1126:
1104:
1100:
1076:
1067:
1063:
1057:
1015:
1011:
1004:
985:
981:
946:
942:
908:
904:
899:
877:
873:
871:
868:
867:
860:
825:
821:
819:
816:
815:
798:
794:
792:
789:
788:
777:
775:Related results
726:
722:
720:
717:
716:
698:
677:
655:
652:
651:
635:
632:
631:
628:Euler's formula
600:
596:
594:
591:
590:
573:
569:
567:
564:
563:
562:The two graphs
544:
541:
540:
520:
517:
516:
493:
489:
487:
484:
483:
466:
462:
460:
457:
456:
440:
437:
436:
420:
417:
416:
407:
400:
380:hypercube graph
369:
341:
337:
335:
332:
331:
314:
310:
308:
305:
304:
284:
281:
280:
253:
249:
247:
244:
243:
226:
222:
220:
217:
216:
200:
197:
196:
166:Euclidean plane
158:
122:
118:
116:
113:
112:
87:
83:
81:
78:
77:
36:
24:
17:
12:
11:
5:
1339:
1329:
1328:
1323:
1307:
1306:
1299:
1272:
1265:
1238:
1226:(4): 356–368,
1210:
1200:(2): 228–232,
1184:
1165:(3): 225–241,
1146:
1124:
1111:Smith, Paul A.
1098:
1061:
1055:
1023:Hong, Seok-Hee
1009:
1002:
988:Mehlhorn, Kurt
979:
958:(4): 681–693,
940:
901:
900:
898:
895:
894:
893:
880:
876:
859:
856:
834:
831:
828:
824:
801:
797:
776:
773:
769:Lev Pontryagin
735:
732:
729:
725:
697:
694:
690:branch and cut
676:
673:
659:
639:
609:
606:
603:
599:
576:
572:
548:
535:is known as a
524:
502:
499:
496:
492:
469:
465:
444:
424:
405:
398:
368:
365:
350:
347:
344:
340:
317:
313:
288:
262:
259:
256:
252:
229:
225:
204:
182:Fáry's theorem
176:with straight
157:
154:
131:
128:
125:
121:
105:complete graph
90:
86:
64:, named after
34:
15:
9:
6:
4:
3:
2:
1338:
1327:
1324:
1322:
1321:Planar graphs
1319:
1318:
1316:
1302:
1300:9781846289699
1296:
1292:
1291:
1286:
1285:Murty, U.S.R.
1282:
1276:
1268:
1266:9781439826270
1262:
1258:
1257:
1252:
1248:
1242:
1234:
1229:
1225:
1221:
1214:
1207:
1203:
1199:
1195:
1188:
1180:
1176:
1172:
1168:
1164:
1160:
1156:
1150:
1142:
1138:
1134:
1128:
1120:
1116:
1112:
1108:
1102:
1094:
1090:
1086:
1083:(in French),
1082:
1075:
1071:
1065:
1058:
1052:
1047:
1042:
1038:
1034:
1033:
1028:
1024:
1020:
1019:Mutzel, Petra
1013:
1005:
1003:9780521563291
999:
995:
994:
989:
983:
975:
971:
966:
961:
957:
953:
952:
944:
936:
932:
928:
924:
920:
916:
912:
906:
902:
878:
874:
865:
862:
861:
855:
853:
848:
832:
829:
826:
822:
799:
795:
786:
782:
772:
770:
766:
762:
758:
753:
751:
733:
730:
727:
723:
714:
710:
706:
702:
693:
691:
686:
682:
672:
657:
637:
629:
625:
624:case analysis
607:
604:
601:
597:
574:
570:
560:
546:
538:
522:
500:
497:
494:
490:
467:
463:
442:
422:
411:
404:
397:
393:
389:
385:
381:
377:
373:
364:
348:
345:
342:
338:
315:
311:
302:
286:
278:
260:
257:
254:
250:
227:
223:
202:
194:
190:
185:
183:
179:
178:line segments
175:
171:
170:simple curves
167:
163:
153:
151:
150:utility graph
147:
129:
126:
123:
119:
110:
106:
88:
84:
75:
71:
67:
63:
62:planar graphs
59:
55:
51:
43:
40:
33:
28:
22:
1290:Graph Theory
1289:
1281:Bondy, J. A.
1275:
1255:
1241:
1223:
1219:
1213:
1197:
1193:
1187:
1162:
1158:
1149:
1140:
1136:
1133:Menger, Karl
1127:
1118:
1114:
1107:Frink, Orrin
1101:
1084:
1080:
1064:
1031:
1012:
992:
982:
955:
949:
943:
918:
914:
911:Tutte, W. T.
905:
849:
778:
764:
760:
757:Soviet Union
754:
699:
678:
561:
536:
414:
402:
395:
388:Kuratowski's
387:
301:homeomorphic
186:
162:planar graph
159:
53:
50:graph theory
47:
41:
31:
1251:Zhang, Ping
1087:: 271–283,
1081:Fund. Math.
921:: 743–767,
750:Karl Menger
705:Orrin Frink
681:linear time
189:subdivision
74:subdivision
1315:Categories
897:References
709:Paul Smith
384:non-planar
277:isomorphic
72:that is a
410:subgraphs
408:(bottom)
401:(top) or
156:Statement
1287:(2008),
1253:(2010),
1072:(1930),
858:See also
111:) or of
109:vertices
107:on five
70:subgraph
1179:0625064
1143:: 85–86
974:8348222
935:0158387
763:or the
755:In the
696:History
515:, then
378:that a
37:in the
1297:
1263:
1177:
1053:
1000:
972:
951:J. ACM
933:
785:minors
386:using
1121:: 214
1077:(PDF)
970:S2CID
713:cubic
193:paths
174:drawn
103:(the
1295:ISBN
1261:ISBN
1051:ISBN
998:ISBN
814:and
707:and
589:and
1228:doi
1202:doi
1167:doi
1089:doi
1041:doi
960:doi
923:doi
539:of
482:or
415:If
406:3,3
390:or
382:is
330:or
303:to
279:to
242:or
152:).
144:(a
76:of
60:of
48:In
35:3,3
1317::
1283:;
1224:12
1222:,
1198:24
1196:,
1175:MR
1173:,
1161:,
1141:67
1139:,
1119:36
1117:,
1109:;
1085:15
1079:,
1049:,
1035:,
1025:;
968:,
956:31
954:,
931:MR
929:,
919:13
854:.
363:.
187:A
160:A
52:,
1304:.
1270:.
1230::
1204::
1182:.
1169::
1163:5
1096:.
1091::
1043::
1007:.
977:.
962::
938:.
925::
879:5
875:K
833:3
830:,
827:3
823:K
800:5
796:K
734:3
731:,
728:3
724:K
658:G
638:G
608:3
605:,
602:3
598:K
575:5
571:K
547:G
523:H
501:3
498:,
495:3
491:K
468:5
464:K
443:H
423:G
403:K
399:5
396:K
349:3
346:,
343:3
339:K
316:5
312:K
287:G
261:3
258:,
255:3
251:K
228:5
224:K
203:G
130:3
127:,
124:3
120:K
89:5
85:K
42:G
32:K
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.