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
20:
1030:
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.
1054:
1325:
1298:
1264:
1154:
1036:
1001:
57:
863:
851:
300:
1250:
630:. Additionally, subdividing a graph cannot turn a nonplanar graph into a planar graph: if a subdivision of a graph
188:
73:
38:
409:
145:
69:
1032:
Graph
Drawing: 15th International Symposium, GD 2007, Sydney, Australia, September 24-26, 2007, Revised Papers
371:
1320:
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
108:
1069:
700:
627:
181:
65:
780:
391:
375:
192:
1110:
969:
708:
299:. Equivalently, a finite graph is planar if and only if it does not contain a subgraph that is
1294:
1288:
1280:
1260:
1254:
1218:
Kennedy, John W.; Quintas, Louis V.; Sysło, Maciej M. (1985), "The theorem on planar graphs",
1050:
997:
991:
684:
276:
817:
718:
592:
485:
333:
245:
114:
1227:
1201:
1166:
1088:
1040:
959:
922:
1178:
934:
869:
790:
565:
458:
306:
218:
79:
1174:
1026:
1021:; Schmidt, Jens M. (2007), "Efficient extraction of multiple Kuratowski subdivisions", in
930:
379:
165:
1284:
1246:
1073:
768:
689:
653:
633:
623:
542:
518:
438:
418:
282:
198:
104:
148:
on six vertices, three of which connect to each of the other three, also known as the
1314:
1232:
1205:
1022:
987:
173:
149:
1018:
973:
948:
Williamson, S. G. (September 1984), "Depth-first search and
Kuratowski subgraphs",
756:
383:
177:
169:
161:
61:
49:
1045:
1132:
1106:
910:
784:
749:
712:
704:
680:
68:. It states that a finite graph is planar if and only if it does not contain a
926:
683:, as measured by the size of the input graph. This allows the correctness of a
26:
1135:(1930), "Über plättbare Dreiergraphen und Potenzen nichtplättbarer Graphen",
752:
in 1930. Since then, several new proofs of the theorem have been discovered.
1192:
Burstein, Michael (1978), "Kuratowski-Pontrjagin theorem on planar graphs",
1092:
1170:
711:, also in 1930, but their proof was never published. The special case of
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
950:
184:
this makes no difference to their graph-theoretic characterization.
370:
715:
planar graphs (for which the only minimal forbidden subgraph is
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
872:
820:
793:
721:
656:
636:
595:
568:
545:
521:
488:
461:
441:
421:
336:
309:
285:
248:
221:
201:
117:
82:
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:
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
8:
996:, Cambridge University Press, p. 510,
783:, characterizes the planar graphs by their
622:are nonplanar, as may be shown either by a
44:(9,2), showing that the graph is nonplanar.
787:in terms of the same two forbidden graphs
1231:
1194:Journal of Combinatorial Theory, Series B
1113:(1930), "Irreducible non-planar graphs",
1044:
963:
877:
871:
825:
819:
798:
792:
726:
720:
655:
635:
600:
594:
573:
567:
544:
520:
493:
487:
466:
460:
440:
420:
341:
335:
314:
308:
284:
253:
247:
226:
220:
200:
122:
116:
87:
81:
1259:(5th ed.), CRC Press, p. 237,
168:, and whose edges can be represented by
25:
19:For the point-set topology theorem, see
902:
21:Kuratowski's closure-complement problem
16:On forbidden subgraphs in planar graphs
7:
435:is a graph that contains a subgraph
748:) was also independently proved by
14:
1037:Lecture Notes in Computer Science
180:representing their edges, but by
1157:(1981), "Kuratowski's theorem",
58:forbidden graph characterization
913:(1963), "How to draw a graph",
1:
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
1342:
864:Kelmans–Seymour conjecture
779:A closely related result,
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:
1279:
1278:
1274:
1267:
1247:Chartrand, Gary
1245:
1244:
1240:
1217:
1216:
1212:
1191:
1190:
1186:
1153:
1152:
1148:
1131:
1130:
1126:
1105:
1104:
1100:
1076:
1068:
1067:
1063:
1057:
1016:
1015:
1011:
1004:
986:
985:
981:
947:
946:
942:
909:
908:
904:
899:
873:
868:
867:
860:
821:
816:
815:
794:
789:
788:
777:
775:Related results
722:
717:
716:
698:
677:
652:
651:
632:
631:
628:Euler's formula
596:
591:
590:
569:
564:
563:
562:The two graphs
541:
540:
517:
516:
489:
484:
483:
462:
457:
456:
437:
436:
417:
416:
407:
400:
380:hypercube graph
369:
337:
332:
331:
310:
305:
304:
281:
280:
249:
244:
243:
222:
217:
216:
197:
196:
166:Euclidean plane
158:
118:
113:
112:
83:
78:
77:
36:
24:
17:
12:
11:
5:
1339:
1337:
1329:
1328:
1323:
1313:
1312:
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:
13:
10:
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:
1273:
1268:
1266:9781439826270
1262:
1258:
1257:
1252:
1248:
1242:
1239:
1234:
1229:
1225:
1221:
1214:
1211:
1207:
1203:
1199:
1195:
1188:
1185:
1180:
1176:
1172:
1168:
1164:
1160:
1156:
1150:
1147:
1142:
1138:
1134:
1128:
1125:
1120:
1116:
1112:
1108:
1102:
1099:
1094:
1090:
1086:
1083:(in French),
1082:
1075:
1071:
1065:
1062:
1058:
1052:
1047:
1042:
1038:
1034:
1033:
1028:
1024:
1020:
1019:Mutzel, Petra
1013:
1010:
1005:
1003:9780521563291
999:
995:
994:
989:
983:
980:
975:
971:
966:
961:
957:
953:
952:
944:
941:
936:
932:
928:
924:
920:
916:
912:
906:
903:
896:
878:
874:
865:
862:
861:
857:
855:
853:
848:
832:
829:
826:
822:
799:
795:
786:
782:
774:
772:
770:
766:
762:
758:
753:
751:
733:
730:
727:
723:
714:
710:
706:
702:
695:
693:
691:
686:
682:
674:
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:
366:
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:
155:
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.
