20:
516:
SPQR tree of the graph are connected by a pair of virtual edges, it is possible to flip the orientation of one of the nodes (replacing it by its mirror image) relative to the other one. Additionally, in a P node of the SPQR tree, the different parts of the graph connected to virtual edges of the P node may be arbitrarily
292:
Typically, it is not allowed within an SPQR tree for two S nodes to be adjacent, nor for two P nodes to be adjacent, because if such an adjacency occurred the two nodes could be merged into a single larger node. With this assumption, the SPQR tree is uniquely determined from its graph. When a graph
156:
In a Q node, the associated graph has a single real edge. This trivial case is necessary to handle the graph that has only one edge. In some works on SPQR trees, this type of node does not appear in the SPQR trees of graphs with more than one edge; in other works, all non-virtual edges are required
515:
of the embedding: the faces of the embedding are exactly the nonseparating cycles of the graph. However, for a planar graph (with labeled vertices and edges) that is 2-connected but not 3-connected, there may be greater freedom in finding a planar embedding. Specifically, whenever two nodes in the
368:
Label each split component with a P (a two-vertex split component with multiple edges), an S (a split component in the form of a triangle), or an R (any other split component). While there exist two split components that share a linked pair of virtual edges, and both components have type S or both
364:
Partition the graph into split components; these are graphs that can be formed by finding a pair of separating vertices, splitting the graph at these two vertices into two smaller graphs (with a linked pair of virtual edges having the separating vertices as endpoints), and repeating this splitting
502:) also belongs to a node of type P and R and the components are as described above. If the two vertices are not adjacent then the two components are represented by two paths of the cycle graph associated with the S node and with the SPQR tree nodes attached to those two paths.
361:, one for each endpoint. After this sorting step, parallel edges between the same two vertices will be adjacent to each other in the sorted list and can be split off into a P-node of the eventual SPQR tree, leaving the remaining graph simple.
333:
suggested that the full SPQR tree structure, and not just the list of components, should be constructible in linear time. After an implementation of a slower algorithm for SPQR trees was provided as part of the GDToolkit library,
160:
In an R node, the associated graph is a 3-connected graph that is not a cycle or dipole. The R stands for "rigid": in the application of SPQR trees in planar graph embedding, the associated graph of an R node has a unique planar
365:
process until no more separating pairs exist. The partition found in this way is not uniquely defined, because the parts of the graph that should become S-nodes of the SPQR tree will be subdivided into multiple triangles.
451:
may be the two endpoints of a virtual edge in the graph associated with an R node, in which case the two components are represented by the two subtrees of the SPQR tree formed by removing the corresponding SPQR tree
393:
numbering of the nodes in the tree, and use certain patterns in this numbering to identify pairs of vertices that can separate the graph into smaller components. When a component is found in this way, a
23:
A graph and its SPQR tree. The dashed black lines connect pairs of virtual edges, shown as black; the remaining edges are colored according to the triconnected component they belong to.
700:
82:); these structures were used in efficient algorithms by several other researchers prior to their formalization as the SPQR tree by Di Battista and Tamassia (
60:
70:
The basic structures underlying the SPQR tree, the triconnected components of a graph, and the connection between this decomposition and the planar embeddings of a
338:
provided the first linear-time implementation. As part of this process of implementing this algorithm, they also corrected some errors in the earlier work of
463:
may be the two vertices in the graph associated with a P node that has two or more virtual edges. In this case the components formed by the removal of
667:
389:
away from the root of the tree, for the edges belonging to the tree, and towards the root for all other edges. They then find a special
769:
1150:
789:
722:
1357:
511:
If a planar graph is 3-connected, it has a unique planar embedding up to the choice of which face is the outer face and of
157:
to be represented by Q nodes with one real and one virtual edge, and the edges in the other node types must all be virtual.
901:
706:
685:
1413:
1017:
631:
Bienstock, Daniel; Monma, Clyde L. (1988), "On the complexity of covering vertices by faces in a planar graph",
1423:
1418:
275:; the order of performing the gluing steps does not affect the result. Each vertex in one of the graphs
982:
395:
386:
867:
737:
325:
The problem of constructing the triconnected components of a graph was first solved in linear time by
250:
into another single supervertex, and deleting the two virtual edges. That is, the larger graph is the
55:, to represent the triconnected components of a graph. The SPQR tree of a graph may be constructed in
1367:
353:
Sort the edges of the graph by the pairs of numerical indices of their endpoints, using a variant of
150:
135:
645:
923:
126:. The node, and the graph associated with it, may have one of four types, given the initials SPQR:
297:
is represented by an SPQR tree with no adjacent P nodes and no adjacent S nodes, then the graphs
894:
640:
1061:
910:
529:
1051:
1006:
8:
1165:
103:
44:
1332:
1291:
1117:
1107:
1021:
986:
941:
541:
535:
378:
306:
associated with the nodes of the SPQR tree are known as the triconnected components of
134:
with three or more vertices and edges. This case is analogous to series composition in
39:
are a system of smaller graphs that describe all of the 2-vertex cuts in the graph. An
774:, Lecture Notes in Computer Science, vol. 1984, Springer-Verlag, pp. 77–90,
1226:
927:
887:
837:
785:
718:
681:
75:
36:
471:
are represented by subtrees of the SPQR tree, one for each virtual edge in the node.
1317:
849:
823:
815:
775:
752:
733:
710:
696:
673:
663:
650:
439:
leaves a disconnected graph, and the connected components of the remaining graphs:
111:
48:
853:
1261:
1011:
52:
538:, a different tree structure that characterizes the edge connectivity of a graph
382:
1214:
1209:
1092:
1026:
268:. Performing this gluing step on each edge of the SPQR tree produces the graph
756:
1407:
1362:
1342:
1185:
1074:
1001:
803:
799:
512:
64:
780:
677:
482:
may be two vertices in the graph associated with an S node such that either
1322:
1286:
1102:
1097:
1079:
991:
936:
765:
142:
71:
28:
702:
Proc. 17th
International Colloquium on Automata, Languages and Programming
1372:
1337:
1327:
1241:
1175:
1170:
1160:
1069:
918:
517:
358:
319:
131:
56:
840:(1937), "A structural characterization of planar combinatorial graphs",
398:
is used to identify the edges that should be part of the new component.
369:
have type P, merge them into a single larger component of the same type.
318:
The SPQR tree of a given 2-vertex-connected graph can be constructed in
1382:
1352:
1312:
1155:
1084:
1031:
951:
879:
714:
415:(without Q nodes) it is straightforward to find every pair of vertices
354:
251:
146:
115:
1347:
1194:
1122:
1112:
828:
819:
654:
588:, both of which are cited as precedents by Di Battista and Tamassia.
149:
to a cycle graph. This case is analogous to parallel composition in
1392:
1276:
1266:
1246:
1219:
1204:
966:
956:
390:
169:
between two nodes of the SPQR tree is associated with two directed
873:
1377:
1281:
1256:
1199:
1046:
976:
971:
946:
532:, a similar tree structure for the 2-vertex-connected components
1296:
1271:
1251:
1236:
1145:
1036:
961:
506:
669:
Proc. 30th Annual
Symposium on Foundations of Computer Science
145:, a multigraph with two vertices and three or more edges, the
19:
1140:
1041:
996:
771:
1132:
874:
The tree of the triconnected components Java implementation
520:. All planar representations may be described in this way.
381:
to find a structure that they call a palm tree; this is a
806:(1973), "Dividing a graph into triconnected components",
768:(2001), "A linear time implementation of SPQR-trees",
282:
may be associated in this way with a unique vertex in
194:
may be a virtual edge for at most one SPQR tree edge.
560:
558:
709:, vol. 443, Springer-Verlag, pp. 598–611,
699:(1990), "On-line graph algorithms with SPQR-trees",
544:, a generalization (no longer unique) to larger cuts
731:
694:
661:
608:
602:
494:
is virtual. If the edge is virtual, then the pair (
330:
91:
87:
83:
16:
Representation of a graph's triconnected components
555:
1405:
763:
568:
374:
346:
335:
798:
630:
585:
581:
564:
339:
326:
895:
208:, formed as follows. Whenever SPQR tree edge
507:Representing all embeddings of planar graphs
289:, the supervertex into which it was merged.
902:
888:
827:
779:
666:(1989), "Incremental planarity testing",
644:
909:
836:
614:
406:
234:, form a single larger graph by merging
130:In an S node, the associated graph is a
79:
18:
876:in the jBPT library (see TCTree class).
598:
596:
594:
141:In a P node, the associated graph is a
1406:
349:includes the following overall steps.
883:
180:and the other of which is an edge in
870:in the Open Graph Drawing Framework.
591:
242:into a single supervertex, merging
13:
102:An SPQR tree takes the form of an
14:
1435:
861:
707:Lecture Notes in Computer Science
603:Di Battista & Tamassia (1989)
331:Di Battista & Tamassia (1996)
59:and has several applications in
313:
201:represents a 2-connected graph
31:, a branch of mathematics, the
574:
490:are not adjacent, or the edge
411:With the SPQR tree of a graph
373:To find the split components,
153:; the P stands for "parallel".
1:
854:10.1215/S0012-7094-37-00336-3
624:
569:Gutwenger & Mutzel (2001)
375:Gutwenger & Mutzel (2001)
347:Gutwenger & Mutzel (2001)
336:Gutwenger & Mutzel (2001)
173:, one of which is an edge in
74:, were first investigated by
586:Bienstock & Monma (1988)
582:Hopcroft & Tarjan (1973)
565:Hopcroft & Tarjan (1973)
340:Hopcroft & Tarjan (1973)
327:Hopcroft & Tarjan (1973)
212:associates the virtual edge
138:; the S stands for "series".
97:
7:
738:"On-line planarity testing"
523:
329:. Based on this algorithm,
10:
1440:
1305:
1184:
1131:
1060:
917:
842:Duke Mathematical Journal
808:SIAM Journal on Computing
757:10.1137/S0097539794280736
745:SIAM Journal on Computing
633:SIAM Journal on Computing
357:that makes two passes of
1358:Left-child right-sibling
868:SPQR tree implementation
548:
401:
61:dynamic graph algorithms
51:, and more specifically
1414:Trees (data structures)
1188:data partitioning trees
1146:C-trie (compressed ADT)
781:10.1007/3-540-44541-2_8
732:Di Battista, Giuseppe;
695:Di Battista, Giuseppe;
678:10.1109/SFCS.1989.63515
662:Di Battista, Giuseppe;
383:depth-first search tree
187:. Each edge in a graph
110:there is associated an
106:in which for each node
33:triconnected components
223:with the virtual edge
151:series–parallel graphs
136:series–parallel graphs
24:
1424:Graph data structures
407:Finding 2-vertex cuts
76:Saunders Mac Lane
22:
1368:Log-structured merge
911:Tree data structures
764:Gutwenger, Carsten;
672:, pp. 436–441,
396:stack data structure
427:such that removing
45:tree data structure
1419:Graph connectivity
1333:Fractal tree index
928:associative arrays
838:Mac Lane, Saunders
715:10.1007/BFb0032061
542:Tree decomposition
379:depth-first search
25:
1401:
1400:
791:978-3-540-41554-1
734:Tamassia, Roberto
724:978-3-540-52826-5
697:Tamassia, Roberto
664:Tamassia, Roberto
474:The two vertices
455:The two vertices
443:The two vertices
345:The algorithm of
37:biconnected graph
1431:
904:
897:
890:
881:
880:
856:
832:
831:
794:
783:
759:
742:
727:
690:
657:
648:
618:
612:
606:
600:
589:
578:
572:
562:
112:undirected graph
53:graph algorithms
49:computer science
1439:
1438:
1434:
1433:
1432:
1430:
1429:
1428:
1404:
1403:
1402:
1397:
1301:
1180:
1127:
1056:
1052:Weight-balanced
1007:Order statistic
921:
913:
908:
864:
820:10.1137/0202012
792:
740:
725:
688:
655:10.1137/0217004
646:10.1.1.542.2314
627:
622:
621:
615:Mac Lane (1937)
613:
609:
601:
592:
579:
575:
563:
556:
551:
526:
509:
409:
404:
385:with its edges
316:
305:
287:
280:
273:
266:
259:
232:
221:
206:
192:
185:
178:
125:
100:
17:
12:
11:
5:
1437:
1427:
1426:
1421:
1416:
1399:
1398:
1396:
1395:
1390:
1385:
1380:
1375:
1370:
1365:
1360:
1355:
1350:
1345:
1340:
1335:
1330:
1325:
1320:
1315:
1309:
1307:
1303:
1302:
1300:
1299:
1294:
1289:
1284:
1279:
1274:
1269:
1264:
1259:
1254:
1249:
1244:
1239:
1234:
1217:
1212:
1207:
1202:
1197:
1191:
1189:
1182:
1181:
1179:
1178:
1173:
1168:
1166:Ternary search
1163:
1158:
1153:
1148:
1143:
1137:
1135:
1129:
1128:
1126:
1125:
1120:
1115:
1110:
1105:
1100:
1095:
1090:
1082:
1077:
1072:
1066:
1064:
1058:
1057:
1055:
1054:
1049:
1044:
1039:
1034:
1029:
1024:
1014:
1009:
1004:
999:
994:
989:
979:
974:
969:
964:
959:
954:
949:
944:
939:
933:
931:
915:
914:
907:
906:
899:
892:
884:
878:
877:
871:
863:
862:External links
860:
859:
858:
848:(3): 460–472,
834:
814:(3): 135–158,
804:Tarjan, Robert
800:Hopcroft, John
796:
790:
761:
751:(5): 956–997,
729:
723:
692:
686:
659:
626:
623:
620:
619:
607:
590:
573:
553:
552:
550:
547:
546:
545:
539:
536:Gomory–Hu tree
533:
530:Block-cut tree
525:
522:
508:
505:
504:
503:
472:
453:
408:
405:
403:
400:
371:
370:
366:
362:
315:
312:
301:
285:
278:
271:
264:
257:
230:
219:
204:
190:
183:
176:
163:
162:
158:
154:
139:
121:
99:
96:
15:
9:
6:
4:
3:
2:
1436:
1425:
1422:
1420:
1417:
1415:
1412:
1411:
1409:
1394:
1391:
1389:
1386:
1384:
1381:
1379:
1376:
1374:
1371:
1369:
1366:
1364:
1361:
1359:
1356:
1354:
1351:
1349:
1346:
1344:
1343:Hash calendar
1341:
1339:
1336:
1334:
1331:
1329:
1326:
1324:
1321:
1319:
1316:
1314:
1311:
1310:
1308:
1304:
1298:
1295:
1293:
1290:
1288:
1285:
1283:
1280:
1278:
1275:
1273:
1270:
1268:
1265:
1263:
1260:
1258:
1255:
1253:
1250:
1248:
1245:
1243:
1240:
1238:
1235:
1232:
1230:
1224:
1222:
1218:
1216:
1213:
1211:
1208:
1206:
1203:
1201:
1198:
1196:
1193:
1192:
1190:
1187:
1183:
1177:
1174:
1172:
1169:
1167:
1164:
1162:
1159:
1157:
1154:
1152:
1149:
1147:
1144:
1142:
1139:
1138:
1136:
1134:
1130:
1124:
1121:
1119:
1118:van Emde Boas
1116:
1114:
1111:
1109:
1108:Skew binomial
1106:
1104:
1101:
1099:
1096:
1094:
1091:
1089:
1087:
1083:
1081:
1078:
1076:
1073:
1071:
1068:
1067:
1065:
1063:
1059:
1053:
1050:
1048:
1045:
1043:
1040:
1038:
1035:
1033:
1030:
1028:
1025:
1023:
1019:
1015:
1013:
1010:
1008:
1005:
1003:
1000:
998:
995:
993:
990:
988:
987:Binary search
984:
980:
978:
975:
973:
970:
968:
965:
963:
960:
958:
955:
953:
950:
948:
945:
943:
940:
938:
935:
934:
932:
929:
925:
920:
916:
912:
905:
900:
898:
893:
891:
886:
885:
882:
875:
872:
869:
866:
865:
855:
851:
847:
843:
839:
835:
830:
825:
821:
817:
813:
809:
805:
801:
797:
793:
787:
782:
777:
773:
772:
767:
766:Mutzel, Petra
762:
758:
754:
750:
746:
739:
735:
730:
726:
720:
716:
712:
708:
704:
703:
698:
693:
689:
687:0-8186-1982-1
683:
679:
675:
671:
670:
665:
660:
656:
652:
647:
642:
638:
634:
629:
628:
616:
611:
604:
599:
597:
595:
587:
583:
577:
570:
566:
561:
559:
554:
543:
540:
537:
534:
531:
528:
527:
521:
519:
514:
501:
497:
493:
489:
485:
481:
477:
473:
470:
466:
462:
458:
454:
450:
446:
442:
441:
440:
438:
434:
430:
426:
422:
418:
414:
399:
397:
392:
388:
384:
380:
376:
367:
363:
360:
356:
352:
351:
350:
348:
343:
341:
337:
332:
328:
323:
321:
311:
309:
304:
300:
296:
290:
288:
281:
274:
267:
260:
253:
249:
245:
241:
237:
233:
226:
222:
215:
211:
207:
200:
197:An SPQR tree
195:
193:
186:
179:
172:
171:virtual edges
168:
159:
155:
152:
148:
144:
140:
137:
133:
129:
128:
127:
124:
120:
117:
113:
109:
105:
104:unrooted tree
95:
93:
89:
85:
81:
77:
73:
68:
66:
65:graph drawing
62:
58:
54:
50:
46:
42:
38:
34:
30:
21:
1387:
1228:
1220:
1085:
1018:Left-leaning
924:dynamic sets
919:Search trees
845:
841:
811:
807:
770:
748:
744:
701:
668:
639:(1): 53–76,
636:
632:
610:
576:
510:
499:
495:
491:
487:
483:
479:
475:
468:
464:
460:
456:
448:
444:
436:
432:
428:
424:
420:
416:
412:
410:
372:
344:
324:
317:
314:Construction
307:
302:
298:
294:
291:
283:
276:
269:
262:
255:
252:2-clique-sum
247:
243:
239:
235:
228:
224:
217:
213:
209:
202:
198:
196:
188:
181:
174:
170:
166:
164:
143:dipole graph
122:
118:
107:
101:
72:planar graph
69:
40:
32:
29:graph theory
26:
1318:Exponential
1306:Other trees
513:orientation
359:bucket sort
320:linear time
147:planar dual
132:cycle graph
57:linear time
1408:Categories
1262:Priority R
1012:Palindrome
625:References
355:radix sort
165:Each edge
161:embedding.
116:multigraph
1348:iDistance
1227:implicit
1215:Hilbert R
1210:Cartesian
1093:Fibonacci
1027:Scapegoat
1022:Red–black
829:1813/6037
641:CiteSeerX
98:Structure
41:SPQR tree
1363:Link/cut
1075:Binomial
1002:Interval
736:(1996),
524:See also
518:permuted
391:preorder
387:oriented
47:used in
1323:Fenwick
1287:Segment
1186:Spatial
1103:Pairing
1098:Leftist
1020:)
992:Dancing
985:)
983:Optimal
78: (
1373:Merkle
1338:Fusion
1328:Finger
1252:Octree
1242:Metric
1176:Y-fast
1171:X-fast
1161:Suffix
1080:Brodal
1070:Binary
788:
721:
684:
643:
580:E.g.,
43:is a
1383:Range
1353:K-ary
1313:Cover
1156:Radix
1141:Ctrie
1133:Tries
1062:Heaps
1042:Treap
1032:Splay
997:HTree
952:(a,b)
942:2–3–4
741:(PDF)
549:Notes
452:edge.
435:from
402:Usage
35:of a
1388:SPQR
1267:Quad
1195:Ball
1151:Hash
1123:Weak
1113:Skew
1088:-ary
786:ISBN
719:ISBN
682:ISBN
584:and
486:and
478:and
467:and
459:and
447:and
431:and
419:and
377:use
261:and
246:and
238:and
92:1996
88:1990
84:1989
80:1937
63:and
1393:Top
1247:MVP
1205:BSP
957:AVL
937:2–3
850:doi
824:hdl
816:doi
776:doi
753:doi
711:doi
674:doi
651:doi
423:in
254:of
227:of
216:of
114:or
94:).
27:In
1410::
1378:PQ
1292:VP
1282:R*
1277:R+
1257:PH
1231:-d
1223:-d
1200:BK
1047:UB
972:B*
967:B+
947:AA
844:,
822:,
810:,
802:;
784:,
749:25
747:,
743:,
717:,
705:,
680:,
649:,
637:17
635:,
593:^
567:;
557:^
492:uv
342:.
322:.
310:.
225:cd
214:ab
210:xy
167:xy
90:,
86:,
67:.
1297:X
1272:R
1237:M
1233:)
1229:k
1225:(
1221:k
1086:d
1037:T
1016:(
981:(
977:B
962:B
930:)
926:/
922:(
903:e
896:t
889:v
857:.
852::
846:3
833:.
826::
818::
812:2
795:.
778::
760:.
755::
728:.
713::
691:.
676::
658:.
653::
617:.
605:.
571:.
500:v
498:,
496:u
488:v
484:u
480:v
476:u
469:v
465:u
461:v
457:u
449:v
445:u
437:G
433:v
429:u
425:G
421:v
417:u
413:G
308:G
303:x
299:G
295:G
286:T
284:G
279:x
277:G
272:T
270:G
265:y
263:G
258:x
256:G
248:d
244:b
240:c
236:a
231:y
229:G
220:x
218:G
205:T
203:G
199:T
191:x
189:G
184:y
182:G
177:x
175:G
123:x
119:G
108:x
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
