363:) is computed. This is one of the two current state-of-the-art algorithms today (the other one is the planarity testing algorithm of de Fraysseix, Ossona de Mendez and Rosenstiehl). See for an experimental comparison with a preliminary version of the Boyer and Myrvold planarity test. Furthermore, the BoyerâMyrvold test was extended to extract multiple Kuratowski subdivisions of a non-planar input graph in a running time linearly dependent on the output size. The source code for the planarity test and the extraction of multiple Kuratowski subdivisions is publicly available. Algorithms that locate a Kuratowski subgraph in linear time in vertices were developed by Williamson in the 1980s.
387:
allows to reduce the planarity test to just testing for each step whether the next added edge has both ends in the external face of the current embedding. While this is conceptually very simple (and gives linear running time), the method itself suffers from the complexity of finding the construction sequence.
386:
and is defined in such a way that every intermediate graph on the way to the full component is again 3-connected. Since such graphs have a unique embedding (up to flipping and the choice of the external face), the next bigger graph, if still planar, must be a refinement of the former graph. This
324:
data structure. With these improvements it is linear-time and outperforms the path addition method in practice. This method was also extended to allow a planar embedding (drawing) to be efficiently computed for a planar graph. In 1999, Shih and Hsu simplified these methods using the PC tree (an
399:
model, in which one maintains an answer to a problem (in this case planarity) as the graph undergoes local updates, typically in the form of insertion/deletion of edges. In the edge-arrival case, there is an asympotically tight
167:
The
FraysseixâRosenstiehl planarity criterion can be used directly as part of algorithms for planarity testing, while Kuratowski's and Wagner's theorems have indirect applications: if an algorithm can find a copy of
349:) algorithm, originally inspired by the PQ tree method, which gets rid of the PQ tree and uses edge additions to compute a planar embedding, if possible. Otherwise, a Kuratowski subdivision (of either
405:
927:
Boyer, John M.; Cortese, P. F.; Patrignani, M.; Battista, G. D. (2003), "Stop minding your P's and Q's: implementing a fast and simple DFS-based planarity testing and embedding algorithm",
408:, improving upon algorithms by Di Battista, Tamassia, and Westbrook. In the fully-dynamic case where edges are both inserted and deleted, there is a logarithmic update-time lower bound by
79:
Planarity testing algorithms typically take advantage of theorems in graph theory that characterize the set of planar graphs in terms that are independent of graph drawings. These include
421:
417:
1246:
Holm, Jacob; Rotenberg, Eva (2020). "Fully-dynamic planarity testing in polylogarithmic time". In
Makarychev, Konstantin; Makarychev, Yury; Tulsiani, Madhur; Kamath, Gautam;
1283:
Eppstein, David; Galil, Zvi; Italiano, Giuseppe; Spencer, Thomas (1996), "Separator based sparsification: I. planarity testing and minimum spanning trees",
317:
313:
277:
371:
A different method uses an inductive construction of 3-connected graphs to incrementally build planar embeddings of every 3-connected component of
1353:
265:
280:. In 2012, Taylor extended this algorithm to generate all permutations of cyclic edge-order for planar embeddings of biconnected components.
156:
814:
1057:
Automata, Languages, and
Programming; Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP'14)
185:
Other planarity criteria, that characterize planar graphs mathematically but are less central to planarity testing algorithms, include:
639:
1199:
953:
928:
409:
1072:
971:
223:
1252:
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of
Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020
292:
of the given graph, and adding vertices one at a time to this data structure. These methods began with an inefficient O(
934:
199:
1117:
Di
Battista, Giuseppe; Tamassia, Roberto (1996), "on-line maintenance of triconnected components with SPQR-trees",
189:
182:
within a given graph, it can be sure that the input graph is not planar and return without additional computation.
1223:
35:(that is, whether it can be drawn in the plane without edge intersections). This is a well-studied problem in
87:
63:. Rather than just being a single Boolean value, the output of a planarity testing algorithm may be a planar
958:. Lecture Notes in Computer Science. Vol. 4875. Sydney, Australia: Springer-Verlag. pp. 159â170.
396:
1307:
Galil, Zvi; Italiano, Giuseppe; Sarnak, Neil (1999), "Fully dynamic planarity testing with applications",
1005:
288:
Vertex addition methods work by maintaining a data structure representing the possible embeddings of an
91:
304:
and
Cederbaum in 1967. It was improved by Even and Tarjan, who found a linear-time solution for the
844:
602:
121:
663:; Cederbaum, I. (1967), "An algorithm for planarity testing of graphs", in Rosenstiehl, P. (ed.),
83:
68:
1348:
597:
60:
908:
739:; Abe, A.; Ozawa, T. (1985), "A linear algorithm for embedding planar graphs using PQâtrees",
256:
was the first published linear-time planarity testing algorithm in 1974. An implementation of
644:
227:
209:
106:
633:
870:
433:
131:
802:
721:, p. 243: âIts implementation in LEDA is slower than LEDA implementations of many other O(
542:
8:
326:
127:
874:
1326:
1255:
1229:
1134:
1100:
1038:
886:
860:
848:
615:
547:
488:
461:
401:
330:
160:
782:
1219:
1087:
La Poutré, Johannes A. (1994), "Alpha algorithms for incremental planarity testing",
1068:
967:
952:; Schmidt, J. M. (2008). "Efficient extraction of multiple Kuratowski subdivisions".
753:
704:
514:
135:
1104:
890:
551:
1330:
1316:
1288:
1265:
1233:
1211:
1182:
1160:
1138:
1126:
1092:
1060:
1042:
1028:
959:
878:
823:
777:
748:
699:
619:
607:
573:
An
Implementation of the Hopcroft and Tarjan Planarity Test and Embedding Algorithm
537:
529:
492:
478:
470:
289:
159:, characterizing planar graphs in terms of a left-right ordering of the edges in a
36:
1089:
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of
Computing (STOC)
588:; NĂ€her, Stefan (1995), "LEDA: A library of efficient data types and algorithms",
1064:
963:
736:
213:
193:
64:
656:
515:"On the Embedding Phase of the Hopcroft and Tarjan Planarity Testing Algorithm"
425:
297:
102:
48:
44:
1208:
Proceedings of the
Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms
882:
1342:
1247:
1186:
904:
798:
683:
585:
564:
506:
456:
452:
342:
269:
261:
257:
253:
249:
217:
117:
1269:
1215:
1293:
1203:
1179:
Automata, Languages and
Programming, 19th International Colloquium, ICALP92
1164:
949:
568:
510:
413:
273:
32:
20:
1321:
1096:
611:
474:
1019:
Williamson, S. G. (1984), "Depth First Search and Kuratowski Subgraphs",
1006:"Boost Graph Library: Boyer-Myrvold Planarity Testing/Embedding - 1.40.0"
679:
660:
301:
203:
1033:
1130:
1059:, Lecture Notes in Computer Science, vol. 8572, pp. 967â978,
842:
828:
533:
865:
483:
429:
40:
28:
124:
on six vertices, three of which connect to each of the other three).
1260:
1177:
Westbrook, Jeffery (1992), "Fast Incremental Planarity Testing",
321:
67:, if the graph is planar, or an obstacle to planarity such as a
926:
1282:
1151:
Tamassia, Roberto (1996), "On-line planar graph embedding",
130:
that a graph is planar if and only if it does not contain a
86:
that a graph is planar if and only if it does not contain a
59:
is the number of edges (or vertices) in the graph, which is
1254:. Association for Computing Machinery. pp. 167â180.
853:
International Journal of Foundations of Computer Science
768:
Shih, W. K.; Hsu, W. L. (1999), "A new planarity test",
991:
734:
947:
424:, improving on sub-linear update-time algorithms by
16:
Algorithmic problem of finding non-crossing drawings
1306:
1116:
1055:Schmidt, Jens M. (2014), "The Mondshein Sequence",
655:
563:
202:characterizing planar graphs by the bases of their
462:Journal of the Association for Computing Machinery
1206:(2004), "Lower Bounds for Dynamic Connectivity",
937:, vol. 2912, Springer-Verlag, pp. 25â36
416:, and a polylogarithmic update-time algorithm by
1340:
1198:
667:, New York: Gordon and Breach, pp. 215â232
366:
505:
451:
266:Library of Efficient Data types and Algorithms
31:problem of testing whether a given graph is a
1245:
584:
43:have emerged, many taking advantage of novel
992:"OGDF - Open Graph Drawing Framework: Start"
930:Proc. 11th Int. Symp. Graph Drawing (GD '03)
815:Journal of Graph Algorithms and Applications
796:
718:
955:Proc. 15th Int. Symp. Graph Drawing (GD'07)
897:
1018:
678:
395:Planarity testing has been studied in the
192:that a graph is planar if and only if its
1320:
1292:
1259:
1176:
1086:
1032:
864:
827:
781:
752:
703:
601:
541:
482:
283:
157:FraysseixâRosenstiehl planarity criterion
1150:
1285:Journal of Computer and System Sciences
1054:
903:
851:(2006), "Trémaux Trees and Planarity",
767:
741:Journal of Computer and System Sciences
459:(1974), "Efficient planarity testing",
336:
325:unrooted variant of the PQ tree) and a
239:
224:Colin de VerdiĂšre's planarity criterion
1354:Computational problems in graph theory
1341:
986:
984:
631:
379:itself). The construction starts with
998:
390:
74:
981:
712:
212:characterizing planar graphs by the
134:(subgraph of a contraction) that is
803:"On the cutting edge: simplified O(
47:. Most of these methods operate in
13:
635:Planarity Testing by Path Addition
14:
1365:
935:Lecture Notes in Computer Science
375:(and hence a planar embedding of
642:from the original on 2016-03-05.
264:'s algorithm is provided in the
1300:
1276:
1239:
1192:
1170:
1144:
1110:
1080:
1048:
1012:
941:
920:
836:
790:
761:
728:
672:
649:
625:
578:
557:
543:11858/00-001M-0000-0014-B51D-B
499:
445:
200:Mac Lane's planarity criterion
1:
910:The left-right planarity test
807:) planarity by edge addition"
783:10.1016/S0304-3975(98)00120-0
725:)-time planarity algorithms.â
638:(Ph.D.). University of Kent.
439:
404:update-time algorithm due to
234:
190:Whitney's planarity criterion
1065:10.1007/978-3-662-43948-7_80
964:10.1007/978-3-540-77537-9_17
770:Theoretical Computer Science
754:10.1016/0022-0000(85)90004-2
705:10.1016/0304-3975(76)90086-4
692:Theoretical Computer Science
367:Construction sequence method
55:) time (linear time), where
7:
10:
1370:
719:Boyer & Myrvold (2004)
632:Taylor, Martyn G. (2012).
883:10.1142/S0129054106004248
590:Communications of the ACM
345:developed a simplified O(
39:for which many practical
1187:10.1007/3-540-55719-9_86
571:; NĂ€her, Stefan (1993),
341:In 2004, John Boyer and
312:-numbering step, and by
122:complete bipartite graph
1270:10.1145/3357713.3384249
1216:10.1145/1007352.1007435
436:, Sarnak, and Spencer.
1294:10.1006/jcss.1996.0002
1165:10.1006/jagm.1996.0044
686:(1976), "Computing an
333:tree of the vertices.
296:) method conceived by
284:Vertex addition method
61:asymptotically optimal
1322:10.1145/300515.300517
1153:Journal of Algorithms
1097:10.1145/195058.195439
612:10.1145/204865.204889
475:10.1145/321850.321852
228:spectral graph theory
1210:, pp. 546â553,
1091:, pp. 706â715,
845:Ossona de Mendez, P.
337:Edge addition method
320:, who developed the
240:Path addition method
84:Kuratowski's theorem
1034:10.1145/1634.322451
875:2006math.....10935D
327:postorder traversal
69:Kuratowski subgraph
1309:Journal of the ACM
1131:10.1007/BF01961541
1021:Journal of the ACM
843:de Fraysseix, H.;
829:10.7155/jgaa.00091
534:10.1007/bf01940648
402:Ackermann function
397:Dynamic Algorithms
391:Dynamic algorithms
331:depth-first search
210:Schnyder's theorem
196:is also cographic,
161:depth-first search
75:Planarity criteria
1074:978-3-662-43947-0
973:978-3-540-77536-2
799:Myrvold, Wendy J.
684:Tarjan, Robert E.
457:Tarjan, Robert E.
216:of an associated
25:planarity testing
1361:
1334:
1333:
1324:
1304:
1298:
1297:
1296:
1280:
1274:
1273:
1263:
1243:
1237:
1236:
1196:
1190:
1189:
1174:
1168:
1167:
1148:
1142:
1141:
1114:
1108:
1107:
1084:
1078:
1077:
1052:
1046:
1045:
1036:
1016:
1010:
1009:
1002:
996:
995:
988:
979:
977:
945:
939:
938:
924:
918:
916:
915:
901:
895:
893:
868:
859:(5): 1017â1030,
840:
834:
832:
831:
811:
797:Boyer, John M.;
794:
788:
786:
785:
776:(1â2): 179â191,
765:
759:
757:
756:
732:
726:
716:
710:
708:
707:
676:
670:
668:
665:Theory of Graphs
653:
647:
643:
629:
623:
622:
605:
582:
576:
575:
561:
555:
554:
545:
519:
503:
497:
495:
486:
449:
290:induced subgraph
128:Wagner's theorem
37:computer science
1369:
1368:
1364:
1363:
1362:
1360:
1359:
1358:
1339:
1338:
1337:
1305:
1301:
1281:
1277:
1244:
1240:
1226:
1200:PÄtraÈcu, Mihai
1197:
1193:
1175:
1171:
1149:
1145:
1115:
1111:
1085:
1081:
1075:
1053:
1049:
1017:
1013:
1004:
1003:
999:
990:
989:
982:
974:
946:
942:
925:
921:
913:
902:
898:
849:Rosenstiehl, P.
841:
837:
809:
795:
791:
766:
762:
733:
729:
717:
713:
677:
673:
654:
650:
630:
626:
583:
579:
562:
558:
517:
504:
500:
450:
446:
442:
393:
384:
369:
362:
355:
339:
286:
242:
237:
214:order dimension
194:graphic matroid
181:
174:
151:
144:
115:
100:
77:
65:graph embedding
45:data structures
27:problem is the
17:
12:
11:
5:
1367:
1357:
1356:
1351:
1336:
1335:
1299:
1275:
1248:Chuzhoy, Julia
1238:
1224:
1191:
1169:
1159:(2): 201â239,
1143:
1125:(4): 302â318,
1109:
1079:
1073:
1047:
1027:(4): 681â693,
1011:
997:
980:
972:
940:
919:
905:Brandes, Ulrik
896:
835:
822:(3): 241â273,
789:
760:
727:
711:
698:(3): 339â344,
671:
648:
624:
603:10.1.1.54.9556
586:Mehlhorn, Kurt
577:
565:Mehlhorn, Kurt
556:
528:(2): 233â242,
507:Mehlhorn, Kurt
498:
469:(4): 549â568,
453:Hopcroft, John
443:
441:
438:
392:
389:
382:
368:
365:
360:
353:
338:
335:
285:
282:
241:
238:
236:
233:
232:
231:
221:
207:
197:
179:
172:
165:
164:
153:
149:
142:
125:
113:
103:complete graph
98:
76:
73:
71:if it is not.
15:
9:
6:
4:
3:
2:
1366:
1355:
1352:
1350:
1349:Planar graphs
1347:
1346:
1344:
1332:
1328:
1323:
1318:
1314:
1310:
1303:
1295:
1290:
1286:
1279:
1271:
1267:
1262:
1257:
1253:
1249:
1242:
1235:
1231:
1227:
1221:
1217:
1213:
1209:
1205:
1204:Demaine, Erik
1201:
1195:
1188:
1184:
1180:
1173:
1166:
1162:
1158:
1154:
1147:
1140:
1136:
1132:
1128:
1124:
1120:
1113:
1106:
1102:
1098:
1094:
1090:
1083:
1076:
1070:
1066:
1062:
1058:
1051:
1044:
1040:
1035:
1030:
1026:
1022:
1015:
1007:
1001:
993:
987:
985:
975:
969:
965:
961:
957:
956:
951:
948:Chimani, M.;
944:
936:
932:
931:
923:
912:
911:
906:
900:
892:
888:
884:
880:
876:
872:
867:
862:
858:
854:
850:
846:
839:
830:
825:
821:
817:
816:
808:
806:
800:
793:
784:
779:
775:
771:
764:
755:
750:
746:
742:
738:
737:Nishizeki, T.
731:
724:
720:
715:
706:
701:
697:
693:
690:-numbering",
689:
685:
681:
675:
666:
662:
658:
652:
646:
641:
637:
636:
628:
621:
617:
613:
609:
604:
599:
596:(1): 96â102,
595:
591:
587:
581:
574:
570:
569:Mutzel, Petra
566:
560:
553:
549:
544:
539:
535:
531:
527:
523:
516:
512:
511:Mutzel, Petra
508:
502:
494:
490:
485:
480:
476:
472:
468:
464:
463:
458:
454:
448:
444:
437:
435:
431:
427:
423:
419:
415:
411:
407:
403:
398:
388:
385:
378:
374:
364:
359:
352:
348:
344:
343:Wendy Myrvold
334:
332:
328:
323:
319:
315:
311:
307:
303:
299:
295:
291:
281:
279:
275:
271:
267:
263:
259:
255:
251:
247:
246:path addition
229:
225:
222:
219:
218:partial order
215:
211:
208:
205:
201:
198:
195:
191:
188:
187:
186:
183:
178:
171:
162:
158:
154:
148:
141:
137:
133:
129:
126:
123:
119:
118:utility graph
112:
108:
104:
97:
93:
89:
85:
82:
81:
80:
72:
70:
66:
62:
58:
54:
50:
46:
42:
38:
34:
30:
26:
22:
1312:
1308:
1302:
1284:
1278:
1251:
1241:
1207:
1194:
1178:
1172:
1156:
1152:
1146:
1122:
1119:Algorithmica
1118:
1112:
1088:
1082:
1056:
1050:
1024:
1020:
1014:
1000:
954:
943:
929:
922:
909:
899:
866:math/0610935
856:
852:
838:
819:
813:
804:
792:
773:
769:
763:
747:(1): 54â76,
744:
740:
730:
722:
714:
695:
691:
687:
680:Even, Shimon
674:
664:
651:
634:
627:
593:
589:
580:
572:
559:
525:
522:Algorithmica
521:
501:
466:
460:
447:
394:
380:
376:
372:
370:
357:
350:
346:
340:
309:
305:
293:
287:
245:
244:The classic
243:
204:cycle spaces
184:
176:
169:
166:
146:
139:
110:
95:
78:
56:
52:
33:planar graph
24:
21:graph theory
18:
735:Chiba, N.;
92:subdivision
29:algorithmic
1343:Categories
1261:1911.03449
1225:1581138520
950:Mutzel, P.
657:Lempel, A.
440:References
248:method of
235:Algorithms
136:isomorphic
90:that is a
41:algorithms
1315:: 28â91,
598:CiteSeerX
484:1813/6011
422:Rotenberg
406:La Poutré
1250:(eds.).
1105:16799743
907:(2009),
891:40107560
801:(2004),
661:Even, S.
640:Archived
552:10014462
513:(1996),
434:Italiano
426:Eppstein
410:PÄtraÈcu
400:inverse-
270:Mehlhorn
258:Hopcroft
250:Hopcroft
107:vertices
105:on five
88:subgraph
1331:7009330
1234:2121130
1139:7838334
1043:8348222
871:Bibcode
645:Alt URL
620:2560175
493:6279825
414:Demaine
329:of the
322:PQ tree
1329:
1232:
1222:
1137:
1103:
1071:
1041:
970:
889:
618:
600:
550:
491:
318:Lueker
298:Lempel
274:Mutzel
262:Tarjan
254:Tarjan
226:using
23:, the
1327:S2CID
1256:arXiv
1230:S2CID
1135:S2CID
1101:S2CID
1039:S2CID
914:(PDF)
887:S2CID
861:arXiv
810:(PDF)
616:S2CID
548:S2CID
518:(PDF)
489:S2CID
430:Galil
314:Booth
278:NĂ€her
220:, and
163:tree.
132:minor
116:(the
109:) or
101:(the
1220:ISBN
1069:ISBN
968:ISBN
420:and
418:Holm
412:and
316:and
302:Even
276:and
260:and
252:and
155:The
120:, a
1317:doi
1289:doi
1266:doi
1212:doi
1183:doi
1161:doi
1127:doi
1093:doi
1061:doi
1029:doi
960:doi
879:doi
824:doi
778:doi
774:223
749:doi
700:doi
608:doi
538:hdl
530:doi
479:hdl
471:doi
361:3,3
356:or
268:by
180:3,3
175:or
150:3,3
145:or
138:to
114:3,3
94:of
19:In
1345::
1325:,
1313:46
1311:,
1287:,
1264:.
1228:,
1218:,
1202:;
1181:,
1157:21
1155:,
1133:,
1123:15
1121:,
1099:,
1067:,
1037:,
1025:31
1023:,
983:^
966:.
933:,
885:,
877:,
869:,
857:17
855:,
847:;
818:,
812:,
772:,
745:30
743:,
694:,
688:st
682:;
659:;
614:,
606:,
594:38
592:,
567:;
546:,
536:,
526:16
524:,
520:,
509:;
487:,
477:,
467:21
465:,
455:;
432:,
428:,
300:,
272:,
1319::
1291::
1272:.
1268::
1258::
1214::
1185::
1163::
1129::
1095::
1063::
1031::
1008:.
994:.
978:.
976:.
962::
917:.
894:.
881::
873::
863::
833:.
826::
820:8
805:n
787:.
780::
758:.
751::
723:n
709:.
702::
696:2
669:.
610::
540::
532::
496:.
481::
473::
383:4
381:K
377:G
373:G
358:K
354:5
351:K
347:n
310:t
308:,
306:s
294:n
230:.
206:,
177:K
173:5
170:K
152:.
147:K
143:5
140:K
111:K
99:5
96:K
57:n
53:n
51:(
49:O
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.