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