230:
855:
364:
117:
1094:
429:
398:
170:
966:. Instead of using a row or column of a grid graph, George partitions the graph into four pieces by using the union of a row and a column as a separator.
488:. More precisely, there is always exactly one or exactly two vertices, which amount to such a separator, depending on whether the tree is
103:
449:
218:
1127:
1075:
110:
206:
81:
1146:
453:
36:
292:
is odd, there is a single central column, and otherwise there are two columns equally close to the center. Choosing
288:
is odd, there is a single central row, and otherwise there are two rows equally close to the center; similarly, if
66:
945:
504:
816:
1063:
41:
939:
187:
91:
339:
1035:
1107:
714:
51:
407:
1051:
379:
71:
27:
149:
1123:
1071:
86:
1089:
1115:
1043:
1011:
904:
198:
61:
452:
On the left a centered tree, on the right a bicentered one. The numbers show each node's
1039:
1085:
1023:
431:
the removal of which partitions it into two connected components, each of size at most
1140:
935:
503:, but that property is most useful for applications in computer science, such as the
493:
489:
138:
626:. The following is a well-known result characterizing the minimal separators:
332:(as in the illustration), then choosing a central column will give a separator
238:
131:
46:
531:-separator, that is, a vertex subset that separates two nonadjacent vertices
460:
229:
56:
448:
300:
from the graph, partitions the graph into two smaller connected subgraphs
884:
883:. It follows from the definition that the predecessor relation yields a
1055:
1015:
781:. More rigorously, the predecessor relation is defined as follows: Let
142:
1119:
1047:
1004:
447:
16:
Set of graph nodes which separate a given pair of nodes if removed
470:
consisting of a single vertex, the removal of which partitions
376:
then choosing a central row will give a separator with at most
1026:(1973), "Nested dissection of a regular finite element mesh",
594:
of nonadjacent vertices. Notice that this is different from
499:
As opposed to these examples, not all vertex separators are
474:
into two or more connected components, each of size at most
296:
to be any of these central rows or columns, and removing
903:
proved that the predecessor relation gives rise to a
819:
410:
382:
342:
152:
1002:
Escalante, F. (1972). "Schnittverbände in
Graphen".
849:
423:
392:
358:
164:
400:vertices. Thus, every grid graph has a separator
938:, a graph in which every minimal separator is a
1095:Journal für die reine und angewandte Mathematik
111:
8:
1114:. Frontiers of Computer Science. Springer.
1068:Algorithmic Graph Theory and Perfect Graphs
582:if it is a minimal separator for some pair
118:
104:
18:
900:
838:
827:
818:
459:To give another class of examples, every
411:
409:
383:
381:
349:
341:
151:
986:
850:{\displaystyle S\sqsubseteq _{a,b}^{G}T}
228:
956:
26:
975:
963:
263:. For instance, in the illustration,
7:
640:is minimal if and only if the graph
614:-separator for any pair of vertices
598:which says that no proper subset of
1112:Graph Separators, with Applications
680:is both adjacent to some vertex in
1028:SIAM Journal on Numerical Analysis
14:
359:{\displaystyle r\leq {\sqrt {n}}}
1090:"Sur les assemblages de lignes"
658:, has two connected components
907:when restricted to the set of
1:
233:A separator for a grid graph.
424:{\displaystyle {\sqrt {n}},}
308:, each of which has at most
82:Strongly connected component
393:{\displaystyle {\sqrt {n}}}
366:vertices, and similarly if
1163:
899:-separators. Furthermore,
249:columns; the total number
165:{\displaystyle S\subset V}
129:
67:K-connectivity certificate
1110:; Heath, Lenwood (2002).
717:: For two fixed vertices
713:-separators also form an
676:such that each vertex in
1064:Golumbic, Martin Charles
946:k-vertex-connected graph
871:, every path connecting
505:planar separator theorem
130:Not to be confused with
650:, obtained by removing
562:if no proper subset of
851:
689:and to some vertex in
596:minimal separating set
456:
425:
394:
360:
234:
166:
42:Algebraic connectivity
852:
765:, if every path from
745:can be regarded as a
451:
426:
395:
361:
232:
167:
817:
809:is a predecessor of
408:
380:
340:
219:connected components
150:
1040:1973SJNA...10..345G
843:
715:algebraic structure
632:A vertex separator
52:Rank (graph theory)
1147:Graph connectivity
1070:, Academic Press,
1016:10.1007/BF02996932
887:on the set of all
847:
823:
574:. More generally,
511:Minimal separators
457:
421:
390:
356:
235:
186:) for nonadjacent
162:
72:Pixel connectivity
28:Graph connectivity
22:Relevant topics on
1108:Rosenberg, Arnold
725:of a given graph
580:minimal separator
416:
388:
354:
128:
127:
87:Biconnected graph
1154:
1133:
1103:
1080:
1058:
1019:
990:
984:
978:
973:
967:
961:
925:
921:
905:complete lattice
901:Escalante (1972)
898:
882:
878:
874:
870:
856:
854:
853:
848:
842:
837:
812:
808:
804:
800:
788:
784:
780:
777:before it meets
776:
772:
768:
764:
760:
744:
740:
728:
724:
720:
712:
697:
688:
679:
675:
666:
657:
653:
649:
639:
635:
625:
613:
601:
593:
577:
573:
569:
565:
557:
542:
538:
534:
530:
518:
487:
486:
485:
481:
473:
469:
466:has a separator
465:
444:
443:
442:
438:
430:
428:
427:
422:
417:
412:
404:of size at most
403:
399:
397:
396:
391:
389:
384:
375:
365:
363:
362:
357:
355:
350:
335:
331:
321:
320:
319:
315:
307:
303:
299:
295:
291:
287:
283:
276:
269:
262:
252:
248:
244:
216:
212:
204:
196:
192:
176:vertex separator
173:
171:
169:
168:
163:
120:
113:
106:
77:Vertex separator
19:
1162:
1161:
1157:
1156:
1155:
1153:
1152:
1151:
1137:
1136:
1130:
1120:10.1007/b115747
1106:
1086:Jordan, Camille
1084:
1078:
1062:
1048:10.1137/0710032
1024:George, J. Alan
1022:
1001:
998:
993:
987:Golumbic (1980)
985:
981:
974:
970:
962:
958:
954:
932:
923:
922:-separators in
911:
888:
880:
876:
872:
858:
815:
814:
810:
806:
802:
801:-separators in
790:
786:
782:
778:
774:
770:
766:
762:
750:
742:
730:
726:
722:
718:
702:
696:
690:
687:
681:
677:
674:
668:
665:
659:
655:
651:
641:
637:
633:
615:
603:
599:
583:
575:
571:
567:
563:
547:
540:
536:
532:
520:
516:
513:
483:
477:
476:
475:
471:
467:
463:
440:
434:
433:
432:
406:
405:
401:
378:
377:
367:
338:
337:
333:
323:
317:
311:
310:
309:
305:
301:
297:
293:
289:
285:
278:
271:
264:
254:
253:of vertices is
250:
246:
242:
227:
214:
210:
202:
194:
190:
148:
147:
145:
135:
124:
62:St-connectivity
17:
12:
11:
5:
1160:
1158:
1150:
1149:
1139:
1138:
1135:
1134:
1128:
1104:
1082:
1076:
1060:
1034:(2): 345–363,
1020:
997:
994:
992:
991:
979:
968:
955:
953:
950:
949:
948:
943:
931:
928:
857:, if for each
846:
841:
836:
833:
830:
826:
822:
694:
685:
672:
663:
512:
509:
420:
415:
387:
353:
348:
345:
226:
223:
217:into distinct
184:separating set
161:
158:
155:
126:
125:
123:
122:
115:
108:
100:
97:
96:
95:
94:
89:
84:
79:
74:
69:
64:
59:
54:
49:
44:
39:
31:
30:
24:
23:
15:
13:
10:
9:
6:
4:
3:
2:
1159:
1148:
1145:
1144:
1142:
1131:
1129:0-306-46464-0
1125:
1121:
1117:
1113:
1109:
1105:
1102:(2): 185–190.
1101:
1098:(in French).
1097:
1096:
1091:
1087:
1083:
1079:
1077:0-12-289260-7
1073:
1069:
1065:
1061:
1057:
1053:
1049:
1045:
1041:
1037:
1033:
1029:
1025:
1021:
1017:
1013:
1009:
1005:
1000:
999:
995:
988:
983:
980:
977:
976:Jordan (1869)
972:
969:
965:
964:George (1973)
960:
957:
951:
947:
944:
941:
937:
936:Chordal graph
934:
933:
929:
927:
919:
915:
910:
906:
902:
896:
892:
886:
869:
865:
861:
844:
839:
834:
831:
828:
824:
820:
813:, in symbols
798:
794:
758:
754:
748:
738:
734:
716:
710:
706:
699:
693:
684:
671:
662:
648:
644:
631:
627:
623:
619:
611:
607:
602:is a minimal
597:
591:
587:
581:
561:
555:
551:
546:
528:
524:
510:
508:
506:
502:
497:
495:
491:
480:
462:
455:
454:eccentricity.
450:
446:
437:
418:
413:
385:
374:
370:
351:
346:
343:
330:
326:
322:vertices. If
314:
281:
274:
267:
261:
257:
240:
231:
224:
222:
220:
208:
200:
189:
185:
181:
177:
159:
156:
153:
144:
140:
133:
121:
116:
114:
109:
107:
102:
101:
99:
98:
93:
90:
88:
85:
83:
80:
78:
75:
73:
70:
68:
65:
63:
60:
58:
55:
53:
50:
48:
45:
43:
40:
38:
35:
34:
33:
32:
29:
25:
21:
20:
1111:
1099:
1093:
1067:
1031:
1027:
1007:
1003:
982:
971:
959:
917:
913:
908:
894:
890:
867:
863:
859:
796:
792:
756:
752:
746:
736:
732:
708:
704:
701:The minimal
700:
691:
682:
669:
660:
646:
642:
629:
628:
621:
617:
609:
605:
595:
589:
585:
579:
578:is called a
559:
553:
549:
544:
526:
522:
514:
500:
498:
478:
458:
435:
372:
368:
328:
324:
312:
279:
272:
265:
259:
255:
236:
183:
179:
175:
139:graph theory
136:
76:
37:Connectivity
1010:: 199–220.
761:-separator
749:of another
747:predecessor
741:-separator
237:Consider a
141:, a vertex
996:References
566:separates
494:bicentered
239:grid graph
209:separates
180:vertex cut
132:cut vertex
47:Cycle rank
825:⊑
560:separator
461:free tree
347:≤
245:rows and
205:from the
157:⊂
57:SPQR tree
1141:Category
1088:(1869).
1066:(1980),
930:See also
885:preorder
501:balanced
490:centered
225:Examples
188:vertices
1056:2156361
1036:Bibcode
909:minimal
805:. Then
789:be two
545:minimal
539:. Then
482:⁄
439:⁄
316:⁄
199:removal
197:if the
172:
146:
1126:
1074:
1054:
940:clique
879:meets
773:meets
630:Lemma.
519:be an
277:, and
143:subset
92:Bridge
1052:JSTOR
952:Notes
729:, an
654:from
543:is a
336:with
284:. If
241:with
207:graph
174:is a
1124:ISBN
1072:ISBN
785:and
721:and
667:and
570:and
535:and
515:Let
304:and
282:= 40
213:and
193:and
178:(or
1116:doi
1044:doi
1012:doi
875:to
769:to
636:in
496:.
492:or
275:= 8
268:= 5
201:of
137:In
1143::
1122:.
1100:70
1092:.
1050:,
1042:,
1032:10
1030:,
1008:38
1006:.
926:.
866:\
862:∈
698:.
645:–
507:.
445:.
371:≤
327:≤
270:,
258:×
221:.
182:,
1132:.
1118::
1081:.
1059:.
1046::
1038::
1018:.
1014::
989:.
942:.
924:G
920:)
918:b
916:,
914:a
912:(
897:)
895:b
893:,
891:a
889:(
881:T
877:b
873:x
868:T
864:S
860:x
845:T
840:G
835:b
832:,
829:a
821:S
811:T
807:S
803:G
799:)
797:b
795:,
793:a
791:(
787:T
783:S
779:T
775:S
771:b
767:a
763:T
759:)
757:b
755:,
753:a
751:(
743:S
739:)
737:b
735:,
733:a
731:(
727:G
723:b
719:a
711:)
709:b
707:,
705:a
703:(
695:2
692:C
686:1
683:C
678:S
673:2
670:C
664:1
661:C
656:G
652:S
647:S
643:G
638:G
634:S
624:)
622:v
620:,
618:u
616:(
612:)
610:v
608:,
606:u
604:(
600:S
592:)
590:b
588:,
586:a
584:(
576:S
572:b
568:a
564:S
558:-
556:)
554:b
552:,
550:a
548:(
541:S
537:b
533:a
529:)
527:b
525:,
523:a
521:(
517:S
484:2
479:n
472:T
468:S
464:T
441:2
436:n
419:,
414:n
402:S
386:n
373:r
369:c
352:n
344:r
334:S
329:c
325:r
318:2
313:n
306:B
302:A
298:S
294:S
290:c
286:r
280:n
273:c
266:r
260:c
256:r
251:n
247:c
243:r
215:b
211:a
203:S
195:b
191:a
160:V
154:S
134:.
119:e
112:t
105:v
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
