17:
129:
Two splits are said to cross if each side of one split has a non-empty intersection with each side of the other split. A split is called strong when it is not crossed by any other split. As a special case, every trivial split is strong. The strong splits of a graph give rise to a structure called the
296:
is the intersection graph of a family of chords of a circle. A given graph is a circle graph if and only if each of the quotients of its split decomposition is a circle graph, so testing whether a graph is a circle graph can be reduced to the same problem on the prime quotient graphs of the graph.
134:
whose leaves correspond one-to-one with the given graph, and whose edges correspond one-to-one with the strong splits of the graph, such that the partition of leaves formed by removing any edge from the tree is the same as the partition of vertices given by the associated strong split.
176:
A graph may have exponentially many different splits, but they are all represented in the split decomposition tree, either as an edge of the tree (for a strong split) or as an arbitrary partition of a complete or star quotient graph (for a split that is not strong).
297:
More, when a circle graph is prime, the combinatorial structure of the set of chords representing it is uniquely determined, which simplifies the task of recognizing this structure. Based on these ideas, it is possible to recognize circle graphs in polynomial time.
343:
These methods can lead to polynomial time algorithms for graphs in which each quotient graph has a simple structure that allows its subproblem to be computed efficiently. For instance, this is true of the graphs in which each quotient graph has constant size.
215:
corresponds to a split, with each side of the split formed by the vertices on one side of the bridge. The cut-set of the split is just the single bridge edge, which is a special case of a complete bipartite subgraph. Similarly, if
313:
algorithm on a bottom-up traversal of its split decomposition tree. At each node we choose the maximum weight independent set on its quotient graph, weighted by the sizes of the independent sets already computed at child
94:
of an undirected graph is a partition of the vertices into two nonempty subsets, the sides of the cut. The subset of edges that have one endpoint in each side is called a cut-set. When a cut-set forms a
279:
is a graph whose split decomposition contains no prime quotients. Based on this characterization, it is possible to use the split decomposition to recognize distance-hereditary graphs in linear time.
165:
corresponding to the leaves in each of the resulting subtrees, and collapsing each of these vertex sets into a single vertex. Every quotient graph has one of three forms: it may be a prime graph, a
126:
A cut or split is trivial when one of its two sides has only one vertex in it; every trivial cut is a split. A graph is said to be prime (with respect to splits) if it has no nontrivial splits.
20:
A graph with two nontrivial strong splits (top) and its split decomposition (bottom). The three quotient graphs are a star (left), a prime graph (center), and a complete graph (right).
232:
and some but not all of the components formed by its deletion are on one side, and the remaining components are on the other side. In these examples, the cut-set of the split forms a
621:
Gioan, Emeric; Paul, Christophe (2012), "Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs",
547:
Dahlhaus, Elias (2000), "Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition",
677:
24:
This article is about cuts that form complete bipartite graphs. For graphs that can be partitioned into a clique and an independent set, see
414:
660:
Cicerone, Serafino; Di
Stefano, Gabriele (1997), "On the equivalence in complexity among basic problems on bipartite and parity graphs",
584:
753:
99:, its cut is called a split. Thus, a split can be described as a partition of the vertices of the graph into two subsets
710:
623:
301:
Split decomposition has also been used to simplify the solution of some problems that are NP-hard on arbitrary graphs:
276:
68:
412:
Charbit, Pierre; de
Montgolfier, Fabien; Raffinot, Mathieu (2012), "Linear time split decomposition revisited",
225:
190:
96:
48:
462:
Gabor, Csaba P.; Supowit, Kenneth J.; Hsu, Wen Lian (1989), "Recognizing circle graphs in polynomial time",
212:
208:
204:
the cycle is a nontrivial split, but for cycles of any longer length there are no nontrivial splits.
63:, which can be constructed in linear time. This decomposition has been used for fast recognition of
310:
233:
170:
131:
130:
split decomposition or join decomposition of the graph. This decomposition can be represented by a
285:
can be recognized in linear time as the graphs in which each split quotient is either complete or
55:
if it has no splits. The splits of a graph can be collected into a tree-like structure called the
632:
464:
423:
221:
91:
44:
673:
582:
Gavoille, Cyril; Paul, Christophe (2003), "Distance labeling scheme and split decomposition",
719:
665:
642:
593:
556:
521:
473:
433:
375:
271:
Split decomposition has been applied in the recognition of several important graph classes:
40:
733:
687:
607:
568:
533:
487:
445:
387:
729:
683:
603:
564:
529:
483:
441:
383:
286:
248:
325:
of a graph by combining computations of weighted maximum cliques in its quotient graphs.
336:
332:
322:
201:
186:
166:
79:
598:
747:
664:, Lecture Notes in Comput. Sci., vol. 1350, Springer, Berlin, pp. 354–363,
708:
Rao, Michaël (2008), "Solving some NP-complete problems using split decomposition",
293:
282:
64:
32:
16:
252:
197:
25:
724:
646:
669:
309:
already observed, the maximum independent set of any graph may be found by a
560:
525:
478:
437:
247:
already showed that it is possible to find the split decomposition in
379:
321:
is flawed, a similar bottom-up traversal can be used to compute the
366:
Cunningham, William H. (1982), "Decomposition of directed graphs",
637:
428:
15:
260:
74:
Splits and split decompositions were first introduced by
200:
of length four, the partition of the vertices given by
78:, who also studied variants of the same notions for
71:, as well as for other problems in graph algorithms.
251:. After subsequent improvements to the algorithm,
512:algorithm for undirected split decomposition",
157:. The quotient graph can be formed by deleting
368:SIAM Journal on Algebraic and Discrete Methods
228:, then the graph has multiple splits in which
161:from the tree, forming subsets of vertices in
261:Charbit, de Montgolfier & Raffinot (2012)
8:
662:Algorithms and computation (Singapore, 1997)
142:of the split decomposition tree of a graph
501:Ma, Tze Heng; Spinrad, Jeremy (1994), "An
318:
306:
244:
153:, called the quotient graph for node
75:
723:
636:
597:
477:
427:
256:
407:
405:
403:
401:
399:
397:
353:
331:also presents algorithms for connected
703:
701:
699:
697:
457:
455:
361:
359:
357:
7:
415:SIAM Journal on Discrete Mathematics
317:Although another algorithm given by
328:
14:
115:is adjacent to every neighbor of
335:, complete dominating sets, and
255:algorithms were discovered by
107:, such that every neighbor of
1:
599:10.1016/S0012-365X(03)00232-2
711:Discrete Applied Mathematics
624:Discrete Applied Mathematics
146:is associated with a graph
770:
69:distance-hereditary graphs
23:
725:10.1016/j.dam.2007.11.013
647:10.1016/j.dam.2011.05.007
277:distance-hereditary graph
670:10.1007/3-540-63890-3_38
193:, every cut is a split.
191:complete bipartite graph
97:complete bipartite graph
49:complete bipartite graph
224:of a graph that is not
211:of a graph that is not
561:10.1006/jagm.2000.1090
526:10.1006/jagm.1994.1007
47:whose cut-set forms a
21:
549:Journal of Algorithms
514:Journal of Algorithms
19:
754:Graph theory objects
585:Discrete Mathematics
479:10.1145/65950.65951
311:dynamic programming
138:Each internal node
57:split decomposition
465:Journal of the ACM
226:2-vertex-connected
222:articulation point
61:join decomposition
22:
718:(14): 2768–2780,
679:978-3-540-63890-2
438:10.1137/10080052X
319:Cunningham (1982)
307:Cunningham (1982)
245:Cunningham (1982)
76:Cunningham (1982)
761:
738:
736:
727:
705:
692:
690:
657:
651:
649:
640:
618:
612:
610:
601:
592:(1–3): 115–130,
579:
573:
571:
544:
538:
536:
511:
498:
492:
490:
481:
459:
450:
448:
431:
409:
392:
390:
363:
231:
219:
213:2-edge-connected
164:
160:
156:
152:
145:
141:
122:
118:
114:
110:
106:
102:
41:undirected graph
769:
768:
764:
763:
762:
760:
759:
758:
744:
743:
742:
741:
707:
706:
695:
680:
659:
658:
654:
620:
619:
615:
581:
580:
576:
546:
545:
541:
502:
500:
499:
495:
461:
460:
453:
411:
410:
395:
380:10.1137/0603021
365:
364:
355:
350:
333:dominating sets
269:
257:Dahlhaus (2000)
249:polynomial time
242:
229:
217:
183:
162:
158:
154:
151:
147:
143:
139:
120:
116:
112:
108:
104:
100:
88:
80:directed graphs
29:
12:
11:
5:
767:
765:
757:
756:
746:
745:
740:
739:
693:
678:
652:
631:(6): 708–733,
613:
574:
555:(2): 205–240,
539:
520:(1): 145–160,
493:
472:(3): 435–473,
451:
422:(2): 499–514,
393:
374:(2): 214–228,
352:
351:
349:
346:
341:
340:
337:graph coloring
326:
323:maximum clique
315:
299:
298:
290:
280:
268:
265:
241:
238:
187:complete graph
182:
179:
167:complete graph
149:
87:
84:
13:
10:
9:
6:
4:
3:
2:
766:
755:
752:
751:
749:
735:
731:
726:
721:
717:
713:
712:
704:
702:
700:
698:
694:
689:
685:
681:
675:
671:
667:
663:
656:
653:
648:
644:
639:
634:
630:
626:
625:
617:
614:
609:
605:
600:
595:
591:
587:
586:
578:
575:
570:
566:
562:
558:
554:
550:
543:
540:
535:
531:
527:
523:
519:
515:
509:
505:
497:
494:
489:
485:
480:
475:
471:
467:
466:
458:
456:
452:
447:
443:
439:
435:
430:
425:
421:
417:
416:
408:
406:
404:
402:
400:
398:
394:
389:
385:
381:
377:
373:
369:
362:
360:
358:
354:
347:
345:
338:
334:
330:
327:
324:
320:
316:
312:
308:
304:
303:
302:
295:
291:
288:
284:
283:Parity graphs
281:
278:
274:
273:
272:
266:
264:
262:
258:
254:
250:
246:
239:
237:
235:
227:
223:
214:
210:
205:
203:
199:
194:
192:
188:
180:
178:
174:
172:
168:
136:
133:
127:
124:
98:
93:
85:
83:
81:
77:
72:
70:
66:
65:circle graphs
62:
58:
54:
51:. A graph is
50:
46:
42:
38:
34:
27:
18:
715:
709:
661:
655:
628:
622:
616:
589:
583:
577:
552:
548:
542:
517:
513:
507:
503:
496:
469:
463:
419:
413:
371:
367:
342:
300:
294:circle graph
270:
267:Applications
243:
206:
195:
184:
175:
137:
128:
125:
89:
73:
60:
56:
52:
36:
33:graph theory
30:
253:linear time
198:cycle graph
86:Definitions
26:split graph
348:References
329:Rao (2008)
240:Algorithms
202:2-coloring
638:0810.1823
429:0902.1700
287:bipartite
748:Category
181:Examples
734:2451095
688:1651043
608:2025945
569:1769515
534:1251842
488:1072233
446:2967479
388:0655562
169:, or a
732:
686:
676:
606:
567:
532:
486:
444:
386:
314:nodes.
220:is an
209:bridge
39:of an
633:arXiv
424:arXiv
196:In a
185:In a
53:prime
43:is a
37:split
674:ISBN
259:and
234:star
171:star
132:tree
103:and
67:and
35:, a
720:doi
716:156
666:doi
643:doi
629:160
594:doi
590:273
557:doi
522:doi
474:doi
434:doi
376:doi
305:As
189:or
119:in
111:in
92:cut
59:or
45:cut
31:In
750::
730:MR
728:,
714:,
696:^
684:MR
682:,
672:,
641:,
627:,
604:MR
602:,
588:,
565:MR
563:,
553:36
551:,
530:MR
528:,
518:16
516:,
484:MR
482:,
470:36
468:,
454:^
442:MR
440:,
432:,
420:26
418:,
396:^
384:MR
382:,
370:,
356:^
292:A
275:A
263:.
236:.
207:A
173:.
123:.
90:A
82:.
737:.
722::
691:.
668::
650:.
645::
635::
611:.
596::
572:.
559::
537:.
524::
510:)
508:n
506:(
504:O
491:.
476::
449:.
436::
426::
391:.
378::
372:3
339:.
289:.
230:v
218:v
163:G
159:i
155:i
150:i
148:G
144:G
140:i
121:X
117:Y
113:Y
109:X
105:Y
101:X
28:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
