31:
451:. It has S-nodes, which are analogous to the series composition operations in series–parallel graphs, P-nodes, which are analogous to the parallel composition operations in series–parallel graphs, and R-nodes, which do not correspond to series–parallel composition operations. A 2-connected graph is series–parallel if and only if there are no R-nodes in its SPQR tree.
360:
for general graphs. The solution capitalizes on the fact that if the answers for one of these problems are known for two SP-graphs, then one can quickly find the answer for their series and parallel compositions.
210:(TTSPG) is a graph that may be constructed by a sequence of series and parallel compositions starting from a set of copies of a single-edge graph
583:
303:
series–parallel graphs, graphs to which no additional edges can be added without destroying their series–parallel structure, are exactly the
671:
628:
333:
SP-graphs may be recognized in linear time and their series–parallel decomposition may be constructed in linear time as well.
595:
17:
295:
at most 2. Indeed, a graph has treewidth at most 2 if and only if it has branchwidth at most 2, if and only if every
69:
There are several ways to define series–parallel graphs. The following definition basically follows the one used by
340:, because a number of standard graph problems are solvable in linear time on SP-graphs, including finding of the
337:
475:
790:
311:
51:
510:
838:
710:
115:
833:
345:
587:
577:
238:, constructed from copies of single-arc graphs, with arcs directed from the source to the sink.
843:
374:
353:
349:
267:
Replacement of a pair of parallel edges with a single edge that connects their common endpoints
336:
Besides being a model of certain types of electric networks, these graphs are of interest in
296:
235:
582:. SIAM Monographs on Discrete Mathematics. and Applications. Vol. 3. Philadelphia, PA:
573:
605:
8:
448:
377:
for the mentioned problems. The class of GSP-graphs include the classes of SP-graphs and
766:
747:
619:
641:
502:
804:
785:
591:
555:
538:
523:
378:
322:
50:, formed recursively by two simple composition operations. They can be used to model
770:
799:
756:
719:
680:
645:
637:
601:
550:
519:
341:
231:, if it is a TTSPG when some two of its vertices are regarded as source and sink.
738:
470:
460:
389:
300:
699:
743:"Linear-time computability of combinatorial problems on series–parallel graphs"
498:
256:
212:
126:
70:
30:
827:
705:
701:
685:
666:
310:
2-connected series–parallel graphs are characterised by having no subgraph
270:
Replacement of a pair of edges incident to a vertex of degree 2 other than
39:
761:
742:
357:
292:
63:
665:
Hall, Rhiannon; Oxley, James; Semple, Charles; Whittle, Geoff (2002).
650:
444:
288:
34:
Series and parallel composition operations for series–parallel graphs
723:
465:
304:
812:
Notices of the BSSR Academy of
Sciences, Ser. Phys.-Math. Sci.
373:(GSP-graphs) are an extension of the SP-graphs with the same
246:
The following definition specifies the same class of graphs.
392:
of a dangling vertex (vertex of degree 1). Alternatively,
321:
Series parallel graphs may also be characterized by their
447:
is a tree structure that can be defined for an arbitrary
736:
708:(1982). "The recognition of series parallel digraphs".
664:
415:
is a TTG created from the disjoint union of graphs
171:
is a TTG created from the disjoint union of graphs
572:
254:. A graph is an SP-graph, if it may be turned into
27:
Recursively-formed graph with two terminal vertices
80:(TTG) is a graph with two distinguished vertices,
46:are graphs with two distinguished vertices called
783:
543:Journal of Mathematical Analysis and Applications
825:
503:"Parallel recognition of series–parallel graphs"
234:In a similar way one may define series–parallel
786:"Combinatorial algorithms on a class of graphs"
497:
396:may be augmented with the following operation.
626:-arboretum of graphs with bounded treewidth".
584:Society for Industrial and Applied Mathematics
568:
566:
536:
57:
576:; Le, Van Bang; Spinrad, Jeremy P. (1999).
563:
328:
263:by a sequence of the following operations:
618:
493:
491:
803:
760:
684:
672:Journal of Combinatorial Theory, Series B
649:
554:
241:
29:
488:
14:
826:
539:"Topology of Series–Parallel Networks"
388:augmented with the third operation of
62:In this context, the term graph means
530:
52:series and parallel electric circuits
667:"On matroids of branch-width three"
24:
693:
371:generalized series–parallel graphs
208:two-terminal series–parallel graph
25:
855:
814:, (1984) no. 3, pp. 109–111
364:
299:is a series–parallel graph. The
287:Every series–parallel graph has
384:GSP graphs may be specified by
338:computational complexity theory
777:
730:
658:
612:
435:become the source and sink of
13:
1:
642:10.1016/S0304-3975(97)00228-4
481:
476:Series-parallel partial order
356:. Some of these problems are
282:
227:. Finally, a graph is called
805:10.1016/0166-218X(94)90022-1
791:Discrete Applied Mathematics
629:Theoretical Computer Science
556:10.1016/0022-247X(65)90125-3
524:10.1016/0890-5401(92)90041-D
7:
511:Information and Computation
454:
114:is a TTG created from the
10:
860:
784:Korneyenko, N. M. (1994).
229:series–parallel (SP-graph)
58:Definition and terminology
711:SIAM Journal on Computing
431:. The source and sink of
423:by merging the source of
219:with assigned terminals.
141:and merging the sinks of
449:2-vertex-connected graph
329:Computational complexity
137:to create the source of
116:disjoint union of graphs
579:Graph classes: a survey
346:maximum independent set
179:by merging the sink of
686:10.1006/jctb.2002.2120
537:Duffin, R. J. (1965).
375:algorithmic efficiency
354:Hamiltonian completion
350:minimum dominating set
242:Alternative definition
191:becomes the source of
149:to create the sink of
44:series–parallel graphs
35:
762:10.1145/322326.322328
297:biconnected component
33:
18:Series-parallel graph
741:; Saito, N. (1982).
199:becomes the sink of
101:parallel composition
622:(1998). "A partial
574:Brandstädt, Andreas
427:with the source of
278:with a single edge.
183:with the source of
748:Journal of the ACM
379:outerplanar graphs
323:ear decompositions
158:series composition
78:two-terminal graph
36:
706:Lawler, Eugene L.
702:Tarjan, Robert E.
597:978-0-898714-32-6
16:(Redirected from
851:
839:Graph operations
818:
817:
810:Translated from
809:
807:
798:(2–3): 215–217.
781:
775:
774:
764:
737:Takamizawa, K.;
734:
728:
727:
700:Valdes, Jacobo;
697:
691:
690:
688:
662:
656:
655:
653:
616:
610:
609:
570:
561:
560:
558:
534:
528:
527:
507:
495:
342:maximum matching
195:and the sink of
187:. The source of
96:, respectively.
21:
859:
858:
854:
853:
852:
850:
849:
848:
824:
823:
822:
821:
815:
782:
778:
735:
731:
724:10.1137/0211023
698:
694:
663:
659:
617:
613:
598:
571:
564:
535:
531:
505:
499:Eppstein, David
496:
489:
484:
471:Hanner polytope
461:Threshold graph
457:
367:
331:
317:
285:
261:
244:
217:
129:the sources of
60:
28:
23:
22:
15:
12:
11:
5:
857:
847:
846:
841:
836:
834:Graph families
820:
819:
776:
755:(3): 623–641.
729:
718:(2): 289–313.
692:
679:(1): 148–171.
657:
620:Bodlaender, H.
611:
596:
562:
549:(2): 303–313.
529:
486:
485:
483:
480:
479:
478:
473:
468:
463:
456:
453:
441:
440:
366:
365:Generalization
363:
330:
327:
315:
291:at most 2 and
284:
281:
280:
279:
268:
259:
243:
240:
215:
71:David Eppstein
59:
56:
26:
9:
6:
4:
3:
2:
856:
845:
844:Planar graphs
842:
840:
837:
835:
832:
831:
829:
813:
806:
801:
797:
793:
792:
787:
780:
772:
768:
763:
758:
754:
750:
749:
744:
740:
739:Nishizeki, T.
733:
725:
721:
717:
713:
712:
707:
703:
696:
687:
682:
678:
674:
673:
668:
661:
652:
647:
643:
639:
636:(1–2): 1–45.
635:
631:
630:
625:
621:
615:
607:
603:
599:
593:
589:
585:
581:
580:
575:
569:
567:
557:
552:
548:
544:
540:
533:
525:
521:
517:
513:
512:
504:
500:
494:
492:
487:
477:
474:
472:
469:
467:
464:
462:
459:
458:
452:
450:
446:
439:respectively.
438:
434:
430:
426:
422:
418:
414:
410:
406:
403:
399:
398:
397:
395:
391:
387:
382:
380:
376:
372:
362:
359:
355:
351:
347:
343:
339:
334:
326:
324:
319:
313:
308:
306:
302:
298:
294:
290:
277:
273:
269:
266:
265:
264:
262:
258:
253:
252:
247:
239:
237:
232:
230:
226:
225:
220:
218:
214:
209:
204:
202:
198:
194:
190:
186:
182:
178:
174:
170:
166:
162:
159:
154:
152:
148:
144:
140:
136:
132:
128:
124:
120:
117:
113:
109:
105:
102:
97:
95:
91:
87:
83:
79:
74:
72:
67:
65:
55:
53:
49:
45:
41:
32:
19:
816:(in Russian)
811:
795:
789:
779:
752:
746:
732:
715:
709:
695:
676:
670:
660:
633:
627:
623:
614:
578:
546:
542:
532:
518:(1): 41–55.
515:
509:
442:
436:
432:
428:
424:
420:
416:
412:
408:
407:of two TTGs
404:
402:source merge
401:
394:Definition 1
393:
386:Definition 2
385:
383:
370:
368:
335:
332:
320:
312:homeomorphic
309:
286:
275:
271:
255:
251:Definition 2
250:
249:
248:
245:
233:
228:
224:Definition 1
223:
222:
221:
211:
207:
205:
200:
196:
192:
188:
184:
180:
176:
172:
168:
164:
163:of two TTGs
161:Sc = Sc(X,Y)
160:
157:
155:
150:
146:
142:
138:
134:
130:
122:
118:
111:
107:
106:of two TTGs
104:Pc = Pc(X,Y)
103:
100:
98:
93:
89:
85:
81:
77:
75:
68:
61:
47:
43:
40:graph theory
37:
586:. pp.
358:NP-complete
293:branchwidth
828:Categories
651:1874/18312
606:0919.05001
482:References
405:S = M(X,Y)
283:Properties
64:multigraph
445:SPQR tree
289:treewidth
48:terminals
771:16082154
501:(1992).
455:See also
390:deletion
236:digraphs
588:172–174
466:Cograph
305:2-trees
301:maximal
127:merging
88:called
769:
604:
594:
90:source
767:S2CID
506:(PDF)
592:ISBN
419:and
411:and
400:The
369:The
352:and
314:to K
175:and
167:and
156:The
145:and
133:and
121:and
110:and
99:The
94:sink
92:and
84:and
800:doi
757:doi
720:doi
681:doi
646:hdl
638:doi
634:209
602:Zbl
551:doi
520:doi
443:An
274:or
125:by
38:In
830::
796:54
794:.
788:.
765:.
753:29
751:.
745:.
716:11
714:.
704:;
677:86
675:.
669:.
644:.
632:.
600:.
590:.
565:^
547:10
545:.
541:.
516:98
514:.
508:.
490:^
381:.
348:,
344:,
325:.
318:.
307:.
206:A
203:.
201:Sc
193:Sc
153:.
151:Pc
139:Pc
76:A
73:.
66:.
54:.
42:,
808:.
802::
773:.
759::
726:.
722::
689:.
683::
654:.
648::
640::
624:k
608:.
559:.
553::
526:.
522::
437:S
433:X
429:Y
425:X
421:Y
417:X
413:Y
409:X
316:4
276:t
272:s
260:2
257:K
216:2
213:K
197:Y
189:X
185:Y
181:X
177:Y
173:X
169:Y
165:X
147:Y
143:X
135:Y
131:X
123:Y
119:X
112:Y
108:X
86:t
82:s
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
