1787:, together with a bounded number of apexes and vortices for each component of the clique-sum. An apex is a vertex that may be adjacent to any other vertex in its component, while a vortex is a graph of bounded pathwidth that is glued into one of the faces of the bounded-genus embedding of a component. The cyclic ordering of the vertices around the face into which a vortex is embedded must be compatible with the path decomposition of the vortex, in the sense that breaking the cycle to form a linear ordering must lead to an ordering with bounded vertex separation number. This theory, in which pathwidth is intimately connected to arbitrary minor-closed graph families, has important algorithmic applications.
2040:. In this application, sentences are modeled as graphs, in which the vertices represent words and the edges represent relationships between words; for instance if an adjective modifies a noun in the sentence then the graph would have an edge between those two words. Due to the limited capacity of human short-term memory, Kornai and Tuza argue that this graph must have bounded pathwidth (more specifically, they argue, pathwidth at most six), for otherwise humans would not be able to parse speech correctly.
1620:
732:
718:
move (arbitrarily, not necessarily along edges) from one vertex to another, and then the fugitive may move along any path in the graph that does not pass through a searcher-occupied vertex. The fugitive is caught when both endpoints of his edge are occupied by searchers. The node searching number of a graph is the minimum number of searchers needed to ensure that the fugitive can be guaranteed to be caught, no matter how he moves. As
473:
885:, the minimum number of edges that cross any cut between lower-numbered and higher-numbered vertices in an optimal linear arrangement of the vertices of a graph; this follows because the vertex separation number, the number of lower-numbered vertices with higher-numbered neighbors, can at most equal the number of cut edges. For similar reasons, the cutwidth is at most the pathwidth times the
183:
1844:, a layout of this type that minimizes the number of vertical tracks on which the lines are to be arranged can be found by computing the pathwidth of a graph that has the lines as its vertices and pairs of lines sharing a gate as its edges. The same algorithmic approach can also be used to model folding problems in
1839:
circuits. In gate matrix layouts, signals are propagated along "lines" (vertical line segments) while each gate of the circuit is formed by a sequence of device features that lie along a horizontal line segment. Thus, the horizontal line segment for each gate must cross the vertical segments for each
1019:
share an endpoint. Any family of graphs has bounded pathwidth if and only if its line graphs have bounded linear clique-width, where linear clique-width replaces the disjoint union operation from clique-width with the operation of adjoining a single new vertex. If a connected graph with three or more
717:
in which a set of searchers collaborate to track down a fugitive hiding in a graph. The searchers are placed on vertices of the graph while the fugitive may be in any edge of the graph, and the fugitive's location and moves are hidden from the searchers. In each turn, some or all of the searchers may
1810:
use interval thickness to model the number of tracks needed in a one-dimensional layout of a VLSI circuit, formed by a set of modules that need to be interconnected by a system of nets. In their model, one forms a graph in which the vertices represent nets, and in which two vertices are connected by
1099:
must be within a constant factor of each other: bounds of this form are known for biconnected outerplanar graphs and for polyhedral graphs. For 2-connected planar graphs, the pathwidth of the dual graph is less than the pathwidth of the line graph. It remains open whether the pathwidth of a planar
1062:
vertices each, and concatenate recursively-constructed path decompositions for each of these two subgraphs. The same technique applies to any class of graphs for which a similar separator theorem holds. Since, like planar graphs, the graphs in any fixed minor-closed graph family have separators of
2076:
On graphs of bounded pathwidth, this approach leads to fixed-parameter tractable algorithms, parametrized by the pathwidth. Such results are not frequently found in the literature because they are subsumed by similar algorithms parametrized by the treewidth; however, pathwidth arises even in
926:
vertices each. A linear arrangement formed by recursively partitioning each of these two subforests, placing the separating vertices between them, has logarithmic vertex searching number. The same technique, applied to a tree-decomposition of a graph, shows that, if the treewidth of an
1647:
and from its path-decomposition without increasing the width. Contraction of an edge, also, can be accomplished without increasing the width of the decomposition, by merging the sub-paths representing the two endpoints of the contracted edge. Therefore, the graphs of pathwidth at most
325:
The second of these two properties is equivalent to requiring that the subsets containing any particular vertex form a contiguous subsequence of the whole sequence. In the language of the later papers in
Robertson and Seymour's graph minor series, a path-decomposition is a
616:
of which the given graph is a subgraph. Interval graphs are a special case of chordal graphs, and chordal graphs can be represented as intersection graphs of subtrees of a common tree generalizing the way that interval graphs are intersection graphs of subpaths of a path.
1823:
of the supergraph, describes an arrangement of the nets along a system of horizontal tracks (one track per color) in such a way that the modules can be placed along the tracks in a linear order and connect to the appropriate nets. The fact that interval graphs are
1871:
The number of parallel lines on which the vertices of a tree can be drawn with no edge crossings (under various natural restrictions on the ways that adjacent vertices can be placed with respect to the sequence of lines) is proportional to the pathwidth of the
68:
such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as
722:
show, the node searching number of a graph equals its interval thickness. The optimal strategy for the searchers is to move the searchers so that in successive turns they form the separating sets of a linear ordering with minimal vertex separation number.
1027:, the pathwidth is at most proportional to the square root of the number of vertices. One way to find a path-decomposition with this width is (similarly to the logarithmic-width path-decomposition of forests described above) to use the
2017:. It is possible to test whether this is the case, using the known fixed-parameter-tractable algorithms for pathwidth, and if so to find a path-decomposition for the undirected graph, in linear time given the assumption that
2779:
credits this result to the 1993 Ph.D. thesis of Ton Kloks; Garbe's polynomial time algorithm for comparability graphs of interval orders generalizes this result, since any chordal graph must be a comparability graph of this
1344:. It follows immediately that it is also NP-complete for the graph families that contain the bipartite distance-hereditary graphs, including the bipartite graphs, chordal bipartite graphs, distance-hereditary graphs, and
190:
with pathwidth 2 and its path-decomposition of width 2. The bottom portion of the image is the same graph and path-decomposition with color added for emphasis. (This example is an adaptation of the graph presented in
4891:
Peng, Sheng-Lung; Ho, Chin-Wen; Hsu, Tsan-sheng; Ko, Ming-Tat; Tang, Chuan Yi (1998), "A linear-time algorithm for constructing an optimal node-search strategy of a tree", in Hsu, Wen-Lian; Kao, Ming-Yang (eds.),
1997:
of the vertices of this DAG represents a valid reordering of the code, and the number of registers needed to evaluate the code in a given ordering is given by the vertex separation number of the ordering.
2096:) shows that, in a cubic graph, the maximum independent set can be constructed in time O(2), faster than previous known methods. A similar approach leads to improved exponential-time algorithms for the
1948:
in such a way that no two edges (represented as straight line segments between grid points) intersect each other. Thus, graphs of bounded pathwidth have embeddings of this type with linear volume.
589:
of the interval graph. For instance, the interval graph shown with its interval representation in the figure has a path decomposition with five nodes, corresponding to its five maximal cliques
1804:
design, the vertex separation problem was originally studied as a way to partition circuits into smaller subsystems, with a small number of components on the boundary between the subsystems.
320:
2013:, the minimum vertex separation among all orderings can be no larger, so the undirected graph formed by ignoring the orientations of the DAG described above must have pathwidth at most
1241:. Nevertheless, several algorithms are known to compute path-decompositions more efficiently when the pathwidth is small, when the class of input graphs is limited, or approximately.
5145:
834:-clique, each maximal clique either separates the graph into two or more components, or it contains a single leaf vertex, a vertex that belongs to only a single maximal clique. A
3509:
2005:
of machine registers, it is possible to determine in linear time whether a piece of straight-line code can be reordered in such a way that it can be evaluated with at most
911:. For, in a forest, one can always find a constant number of vertices the removal of which leaves a forest that can be partitioned into two smaller subforests with at most
1277:
algorithm is applied to this decomposition in order to find the optimal decomposition. However, the time bounds for known algorithms of this type are exponential in
559:
as a subgraph. Its maximal cliques are given by the sets of intervals containing the representative points, and its maximum clique size is one plus the pathwidth of
1351:
However, the pathwidth may be computed in linear time for trees and forests,. It may also be computed in polynomial time for graphs of bounded treewidth including
612:
This equivalence between pathwidth and interval thickness is closely analogous to the equivalence between treewidth and the minimum clique number (minus one) of a
439:
in the first definition of path decompositions, with two vertices in successive induced subgraphs being glued together when they are induced by the same vertex in
1383:
themselves, since in that case the pathwidth is just one less than the maximum number of intervals covering any point in an interval representation of the graph.
4412:
Kashiwabara, T.; Fujisawa, T. (1979), "NP-completeness of the problem of finding a minimum-clique-number interval graph containing a given graph as a subgraph",
1828:
implies that the number of colors needed, in an optimal arrangement of this type, is the same as the clique number of the interval completion of the net graph.
2084:
The same dynamic programming method also can be applied to graphs with unbounded pathwidth, leading to algorithms that solve unparametrized graph problems in
4870:
Ohtsuki, Tatsuo; Mori, Hajimu; Kuh, Ernest S.; Kashiwabara, Toshinobu; Fujisawa, Toshio (1979), "One-dimensional logic gate assignment and interval graphs",
417:
that are glued together by identifying pairs of vertices from consecutive graphs in the sequence, such that the result of performing all of these gluings is
5137:
4826:
Möhring, Rolf H. (1990), "Graph problems related to gate matrix layout and PLA folding", in
Tinhofer, G.; Mayr, E.; Noltemeier, H.; et al. (eds.),
1713:
by connecting a new root vertex by an edge to an arbitrarily chosen vertex in each of the three smaller trees. For instance, the seven-vertex tree in
685:, represented (as in the figure) in such a way that all interval endpoints are distinct, then the ordering of the left endpoints of the intervals of
1438:
by contracting edges, removing edges, and removing vertices. Graph minors have a deep theory in which several important results involve pathwidth.
4413:
4062:
1811:
an edge if their nets both connect to the same module; that is, if the modules and nets are interpreted as forming the nodes and hyperedges of a
5174:
Takahashi, Atsushi; Ueno, Shuichi; Kajitani, Yoji (1994), "Minimal acyclic forbidden minors for the family of graphs with bounded path-width",
4270:
3758:
3296:
Developments in
Theoretical Computer Science (Proc. 7th International Meeting of Young Computer Scientists, Smolenice, 16–20 November 1992)
3412:; Gilbert, John R.; Hafsteinsson, Hjálmtýr; Kloks, Ton (1992), "Approximating treewidth, pathwidth, and minimum elimination tree height",
5088:
Skodinis, Konstantin (2003), "Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time",
4024:
Ferreira, Afonso G.; Song, Siang W. (1992), "Achieving optimality for gate matrix layout and PLA folding: a graph theoretic approach",
1977:
in which the nodes represent the input values to the code and the values computed by the operations within the code. An edge from node
778:
graphs (graphs to which no more edges can be added without increasing the pathwidth) have exactly this many edges. A maximal pathwidth-
1265:, in linear time. In general, these algorithms operate in two phases. In the first phase, the assumption that the graph has pathwidth
4894:
Computing and
Combinatorics, 4th Annual International Conference, COCOON '98, Taipei, Taiwan, R.o.C., August 12–14, 1998, Proceedings
1309:
surveys the complexity of computing the pathwidth on various special classes of graphs. Determining whether the pathwidth of a graph
1895:
distinct horizontal lines, with edges routed as monotonic polygonal paths between these lines, in such a way that there are at most
3885:
3696:
1144:
4625:
Kneis, Joachim; Mölle, Daniel; Richter, Stefan; Rossmanith, Peter (2005), "Algorithms based on the treewidth of sparse graphs",
4157:
Fomin, Fedor V.; Kratsch, Dieter; Todinca, Ioan; Villanger, Yngve (2008), "Exact algorithms for treewidth and minimum fill-in",
1269:
is used to find a path-decomposition or tree-decomposition that is not optimal, but whose width can be bounded as a function of
1103:
In some classes of graphs, it has been proven that the pathwidth and treewidth are always equal to each other: this is true for
877:
Since path-decompositions are a special case of tree-decompositions, the pathwidth of any graph is greater than or equal to its
4847:
3362:
535:
is given. Then one may represent the nodes of the decomposition as points on a line (in path order) and represent each vertex
5126:
5078:
4909:
4642:
4615:
4588:
4555:
4230:
3579:
3537:
3443:
3117:
Arnborg, Stefan (1985), "Efficient algorithms for combinatorial problems on graphs with bounded decomposability – A survey",
3096:
3260:
Björklund, Andreas; Husfeldt, Thore (2008), "Exact algorithms for exact satisfiability and number of perfect matchings",
1222:
is a variable given as part of the input. The best known worst-case time bounds for computing the pathwidth of arbitrary
4569:; Müller, H.; Kratsch, D. (1993), "Computing treewidth and minimum fill-in: all you need are the minimal separators",
3175:
Aspvall, Bengt; Proskurowski, Andrzej; Telle, Jan Arne (2000), "Memory requirements for table computations in partial
4835:
4288:
4079:
4051:
3810:
3776:
3417:
386:
in this definition makes little difference in most applications of pathwidth, but is used to make the pathwidth of a
269:
4677:
Kornai, András; Tuza, Zsolt (1992), "Narrowness, path-width, and their application in natural language processing",
5060:
4570:
4356:
Habib, Michel; Möhring, Rolf H. (1994), "Treewidth of cocomparability graphs and a new order-theoretic parameter",
3986:
3942:
1973:
instead of having to be spilled into main memory. In this application, one represents the code to be compiled as a
1474:
5012:
4980:
4948:
4389:
3237:
1962:
150:
can be solved in an amount of time that depends linearly on the size of the graph but superexponentially on
457:. The width of the path decomposition is then one less than the maximum number of vertices in one of the graphs
5176:
5003:
4971:
4939:
4501:
4443:
4308:
4190:
Fomin, Fedor V.; Thilikos, Dimitrios M. (2007), "On self duality of pathwidth in polyhedral graph embeddings",
4136:
4006:
3960:
3595:
3224:
3076:
1865:
204:
5162:
5219:
5035:
Scheffler, Petra (1990), "A linear algorithm for the pathwidth of trees", in
Bodendiek, R.; Henn, R. (eds.),
4919:
1459:
81:
3909:
Ellis, J. A.; Sudborough, I. H.; Turner, J. S. (1994), "The vertex separation and search number of a tree",
3456:; Gustedt, Jens; Telle, Jan Arne (1998), "Linear-time register allocation for a fixed number of registers",
1020:
vertices has maximum degree three, then its cutwidth equals the vertex separation number of its line graph.
539:
as a closed interval having these points as endpoints. In this way, the path decomposition nodes containing
5007:
4975:
4943:
4679:
4654:
4472:
4333:
3723:
3232:
3228:
3054:
3050:
2088:. For instance, combining this dynamic programming approach with the fact that cubic graphs have pathwidth
208:
30:
5209:
3911:
2037:
1701:
may be precisely characterized: these trees are exactly the trees that can be formed from three trees in
142:
to find the pathwidth of arbitrary graphs, or even to approximate it accurately. However, the problem is
3474:; Kloks, Ton (1996), "Efficient and constructive algorithms for the pathwidth and treewidth of graphs",
1294:
an explicit linear-time algorithm based on a structural decomposition of pathwidth-2 graphs is given by
3874:
3832:
1965:, pathwidth arises in the problem of reordering sequences of straight-line code (that is, code with no
1816:
162:. Many problems in graph algorithms may be solved efficiently on graphs of bounded pathwidth, by using
4240:
Golovach, P. A. (1993), "The cutwidth of a graph and the vertex separation number of the line graph",
4085:
5214:
4159:
3551:
3322:
2131:
1391:
It is NP-hard to approximate the pathwidth of a graph to within an additive constant. The best known
1352:
1341:
1250:
963:
528:, such that the width of the decomposition is one less than the clique number of the interval graph.
143:
132:
2128:, a number that is bounded for a minor-closed graph family if and only if the family excludes a path
4105:
2736:. A chordal domino is a chordal graph in which every vertex belongs to at most two maximal cliques.
1845:
1498:
1028:
3941:; Lee, James R. (2005), "Improved approximation algorithms for minimum-weight vertex separators",
697:
one may derive an interval representation in which the left endpoint of the interval for a vertex
5045:
Scheffler, Petra (1992), "Optimal embedding of a tree into an interval graph in linear time", in
4192:
3673:
2048:
Many problems in graph algorithms may be solved efficiently on graphs of low pathwidth, by using
1764:
120:
4733:
Lopez, Alexander D.; Law, Hung-Fai S. (1980), "A dense gate matrix layout method for MOS VLSI",
1755:
of forbidden minors for pathwidth-2 graphs has been computed; it contains 110 different graphs.
5046:
4778:
4496:
3754:
2116:, a different way of measuring the complexity of an arbitrary graph in terms of interval graphs
2101:
2052:
on a path-decomposition of the graph. For instance, if a linear ordering of the vertices of an
1974:
4441:
Kinnersley, Nancy G. (1992), "The vertex separation number of a graph equals its path-width",
4213:
Garbe, Renate (1995), "Tree-width and path-width of comparability graphs of interval orders",
3635:
2146:, a measure of the complexity of rooted trees defined similarly to pathwidth of unrooted trees
123:
have bounded pathwidth. Pathwidth, and graphs of bounded pathwidth, also have applications in
119:
may be characterized as having bounded pathwidth, and the "vortices" appearing in the general
4429:
3896:
Ellis, J. A.; Sudborough, I. H.; Turner, J. S. (1983), "Graph separation and search number",
1100:
graph and its dual are always within a constant factor of each other in the remaining cases.
886:
61:
3094:
Amini, Omid; Huc, Florian; Pérennes, Stéphane (2009), "On the path-width of planar graphs",
352:
The width of a path-decomposition is defined in the same way as for tree-decompositions, as
5111:
Proc. 33rd
International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007)
4787:
4742:
4627:
Proc. 31st
International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005)
3878:
1994:
4809:
3294:(1994), "A tourist guide through treewidth", in Dassow, Jürgen; Kelemenová, Alisa (eds.),
701:
is its position in the ordering and the right endpoint is the position of the neighbor of
8:
5059:
Skodinis, Konstantin (2000), "Computing optimal linear layouts of trees in linear time",
4134:
Fomin, Fedor V.; Høie, Kjartan (2006), "Pathwidth of cubic graphs and exact algorithms",
3938:
3750:
3593:(1996), "A simple linear-time algorithm for finding path-decompositions of small width",
2049:
2021:
is a constant. Once a path decomposition has been found, a topological ordering of width
1970:
1899:
crossings. The graphs with such drawings have pathwidth that is bounded by a function of
1784:
1573:
1522:
1478:
1392:
1334:
1274:
1154:, or more generally any graph with maximum vertex degree three, the pathwidth is at most
1116:
1095:. For some classes of planar graphs, the pathwidth of the graph and the pathwidth of its
897:
714:
166:
on a path-decomposition of the graph. Path decomposition may also be used to measure the
163:
155:
116:
5113:, Lecture Notes in Computer Science, vol. 4769, Springer-Verlag, pp. 258–269,
5065:, Lecture Notes in Computer Science, vol. 1879, Springer-Verlag, pp. 403–414,
4845:
Monien, B.; Sudborough, I. H. (1988), "Min cut is NP-complete for edge weighted trees",
4746:
4629:, Lecture Notes in Computer Science, vol. 3787, Springer-Verlag, pp. 385–396,
1079:, it follows that the pathwidth of the graphs in any fixed minor-closed family is again
4758:
4721:
4602:, Lecture Notes in Computer Science, vol. 903, Springer-Verlag, pp. 106–120,
4572:
Proc. 1st
European Symposium on Algorithms (ESA'93) (Lecture Notes in Computer Science)
4566:
4532:, Lecture Notes in Computer Science, vol. 650, Springer-Verlag, pp. 116–125,
4525:
4375:
4294:
4257:
4122:
4071:
4028:, Lecture Notes in Computer Science, vol. 583, Springer-Verlag, pp. 139–153,
4012:
3966:
3854:
3782:
3665:
3622:
3604:
3556:, Lecture Notes in Computer Science, vol. 447, Springer-Verlag, pp. 301–309,
3547:
3514:, Lecture Notes in Computer Science, vol. 700, Springer-Verlag, pp. 114–125,
3511:
Proc. 20th
International Colloquium on Automata, Languages and Programming (ICALP 1993)
3508:; Kloks, Ton; Kratsch, Dieter (1993), "Treewidth and pathwidth of permutation graphs",
3505:
3471:
3453:
3409:
3385:
3353:
3317:
3291:
3279:
3198:
3134:
3082:
1376:
548:
327:
104:
5101:
4994:
4600:
Proc. 20th
International Workshop Graph-Theoretic Concepts in Computer Science (WG'94)
4403:
4215:
Proc. 20th International Workshop Graph-Theoretic Concepts in Computer Science (WG'94)
3757:(2005), "Algorithmic graph minor theory: decomposition, approximation, and coloring",
3401:
3376:
3320:(1996), "A linear-time algorithm for finding tree-decompositions of small treewidth",
3057:(1990), "A separator theorem for graphs with an excluded minor and its applications",
5190:
5122:
5074:
4962:
4905:
4861:
4831:
4814:
4693:
4668:
4638:
4611:
4584:
4551:
4515:
4486:
4457:
4347:
4284:
4261:
4226:
4217:, Lecture Notes in Computer Science, vol. 903, Springer-Verlag, pp. 26–37,
4075:
4047:
4002:
3956:
3806:
3772:
3694:
Diestel, Reinhard (1995), "Graph Minors I: a short proof of the path-width theorem",
3618:
3575:
3533:
3439:
3251:
3138:
3072:
2009:
registers. For, if the vertex separation number of a topological ordering is at most
1368:
1356:
1108:
959:
4762:
4725:
4126:
3970:
3890:, Lecture Notes in Computer Science, vol. 2528, Springer-Verlag, pp. 42–53
3786:
3283:
3086:
1915:
are both constant, it is possible in linear time to determine whether a graph has a
609:; the maximum clique size is three and the width of this path decomposition is two.
5185:
5154:
5114:
5097:
5066:
5021:
4989:
4957:
4897:
4879:
4856:
4804:
4796:
4750:
4713:
4704:
4688:
4663:
4630:
4603:
4576:
4541:
4533:
4528:(1992), "Approximating treewidth and pathwidth of some classes of perfect graphs",
4510:
4481:
4467:
4452:
4398:
4379:
4367:
4342:
4317:
4298:
4276:
4249:
4218:
4201:
4176:
4168:
4145:
4114:
4037:
4029:
4016:
3992:
3982:
3948:
3920:
3858:
3846:
3764:
3732:
3705:
3682:
3652:
3626:
3614:
3565:
3557:
3523:
3515:
3491:
3483:
3429:
3421:
3397:
3371:
3339:
3331:
3271:
3246:
3202:
3190:
3163:
3126:
3105:
3062:
2085:
2078:
1330:
1112:
871:
736:
677:. This follows from the earlier equivalence with interval graph clique numbers: if
429:
167:
3866:
3827:; Kitching, M.; Liotta, G.; McCartin, C.; Nishimura, N.; Ragde, P.; Rosamond, F.;
3820:
5118:
4896:, Lecture Notes in Computer Science, vol. 1449, Springer, pp. 279–288,
4387:
Hliněny, Petr (2003), "Crossing-number critical graphs have bounded path-width",
4358:
3978:
3824:
3798:
3590:
2143:
2140:, a different NP-complete optimization problem involving linear layouts of graphs
2137:
1969:
branches or loops) in such a way that all the values computed in the code can be
1819:. An interval representation of a supergraph of this line graph, together with a
1780:
1338:
771:
4433:
3718:
1177:
is the number of vertices in the graph. There exist cubic graphs with pathwidth
1047:
vertices the removal of which separates the graph into two subgraphs of at most
5026:
4322:
3985:(1989), "On search decision and the efficiency of polynomial-time algorithms",
3828:
3298:, Topics in Computer Mathematics, vol. 6, Gordon and Breach, pp. 1–20
2104:
problems in cubic graphs, and for several other NP-hard optimization problems.
1820:
1486:
1380:
1120:
812:
586:
505:
477:
78:
74:
5158:
4269:
Guha, Sudipto (2000), "Nested graph dissection and approximation algorithms",
4149:
4118:
3850:
3737:
3709:
3656:
3388:; Fomin, Fedor V. (2002), "Approximation of pathwidth of outerplanar graphs",
3335:
3275:
2134:, a measure of the sparsity of a graph that is at most equal to its path width
2025:(if one exists) can be found using dynamic programming, again in linear time.
970:
all have bounded treewidth, they all also have at most logarithmic pathwidth.
480:
with pathwidth two, one less than the cardinality of its four maximum cliques
158:, the pathwidth may be computed in polynomial time without dependence on
5203:
5070:
4901:
4883:
4607:
4580:
4537:
4280:
4253:
4222:
3561:
3519:
3147:
1857:
1836:
1825:
1639:, then the same path-decomposition remains valid if any edge is removed from
1326:
799:
613:
128:
4754:
4652:
Korach, Ephraim; Solel, Nir (1993), "Tree-width, path-width, and cutwidth",
3952:
3425:
2122:, the minimum possible width of a linear ordering of the vertices of a graph
1669:
necessarily includes at least one forest, it is not true that all graphs in
4818:
3925:
3837:
3746:
3643:
3487:
3262:
3210:
3181:
1966:
1840:
of the lines that form inputs or outputs of the gate. As in the layouts of
1619:
1572:-minor-free graphs include all forests, and in particular they include the
1482:
1345:
1322:
1024:
974:
630:
22:
4530:
Proc. 3rd International Symposium on Algorithms and Computation (ISAAC'92)
4306:
Gurski, Frank; Wanke, Egon (2007), "Line graphs of bounded clique-width",
3457:
3194:
3067:
5109:
Suchan, Karol; Todinca, Ioan (2007), "Pathwidth of circular-arc graphs",
4026:
Proc. 1st Latin American Symposium on Theoretical Informatics (LATIN '92)
3934:
3768:
2097:
1568:-minor-free graphs do not have bounded pathwidth. For, in this case, the
1427:
1364:
1360:
1211:
1185:
1151:
1138:
967:
870:-path. In particular the maximal graphs of pathwidth one are exactly the
200:
112:
108:
5051:
Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity
4830:, Computing Supplementum, vol. 7, Springer-Verlag, pp. 17–51,
4634:
4470:(1994), "Obstruction set isolation for the gate matrix layout problem",
4272:
Proc. 41st IEEE Symposium on Foundations of Computer Science (FOCS 2000)
3997:
3879:"Path-width and three-dimensional straight-line grid drawings of graphs"
3760:
Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005)
1592:-minor-free-graphs have unbounded pathwidth. In the other direction, if
4717:
4371:
4042:
4033:
3794:
3636:"A Distributed Algorithm for Computing the Node Search Number in Trees"
3150:; Proskurowski, Andrzej (1987), "Complexity of finding embeddings in a
3130:
2125:
1812:
1776:
1125:
1096:
982:
387:
346:
52:
is a number that measures how much the path was thickened to form
41:
4546:
4205:
4172:
3686:
3570:
3550:; Möhring, Rolf H. (1990), "The pathwidth and treewidth of cographs",
3528:
3496:
3434:
3344:
3109:
1868:
have pathwidth that is bounded by a function of their crossing number.
4800:
4782:
4702:
Lengauer, Thomas (1981), "Black-white pebbles and graph separation",
4181:
3870:
3609:
3046:
1379:, for the comparability graphs of interval orders, and of course for
878:
171:
100:
3835:(2008), "On the parameterized complexity of layered graph drawing",
3167:
1450:
of graphs is closed under taking minors (every minor of a member of
973:
As well as its relations to treewidth, pathwidth is also related to
16:
Representation of a graph as a path graph "thickened" by some amount
2119:
2113:
1958:
1517:
are closely related, and the first such result of this type was by
978:
882:
731:
402:
describes, pathwidth can be characterized in many equivalent ways.
3898:
Proc. 1983 Allerton Conf. on Communication, Control, and Computing
3408:
3304:
Bodlaender, Hans L. (1994a), "A tourist guide through treewidth",
2254:
1722:
is formed in this way from the two-vertex tree (a single edge) in
1407:
1767:
for minor-closed graph families states that, for any such family
1525:
in the family of forbidden minors. Specifically, define a family
1465:
can be characterized as the graphs that do not have any minor in
1372:
1104:
657:
or a later vertex as a neighbor. The vertex separation number of
472:
139:
5146:
International Journal of Computational Geometry and Applications
2077:
treewidth-based dynamic programming algorithms in measuring the
1731:. Based on this construction, the number of forbidden minors in
689:
has vertex separation number one less than the clique number of
4103:
Fomin, Fedor V. (2003), "Pathwidth of planar and line graphs",
3222:
2828:
1214:
to determine whether the pathwidth of a given graph is at most
154:. Additionally, for several special classes of graphs, such as
57:
3745:
3459:
Proc. 9th ACM–SIAM Symposium on Discrete Algorithms (SODA '98)
2883:
1560:
In one direction, this result is straightforward to prove: if
1395:
of a polynomial time approximation algorithm for pathwidth is
410:
A path decomposition can be described as a sequence of graphs
3887:
Proc. 10th International Symposium on Graph Drawing (GD 2002)
3819:
3664:
Coudert, David; Huc, Florian; Sereni, Jean-Sébastien (2007),
2974:
2064:, then it is possible to find the maximum independent set of
1685:
consists of two graphs, a seven-vertex tree and the triangle
4598:
Kloks, Ton; Kratsch, Dieter; Müller, H. (1995), "Dominoes",
4564:
4331:
Gustedt, Jens (1993), "On the pathwidth of chordal graphs",
4156:
2748:
2678:
543:
correspond to the representative points in the interval for
182:
4978:(2003), "Graph minors. XVI. Excluding a non-planar graph",
4624:
3944:
Proc. 37th ACM Symposium on Theory of Computing (STOC 2005)
3025:
1832:
1801:
504:
is equal to one less than the smallest clique number of an
124:
99:
Pathwidth and path-decompositions are closely analogous to
3145:
2239:
1414:. For approximations on restricted classes of graphs, see
1406:. For earlier approximation algorithms for pathwidth, see
1257:, it is possible to test whether the pathwidth is at most
1184:, but it is not known how to reduce this gap between this
4869:
4426:
Obstruction set isolation for layout permutation problems
2231:
1841:
1807:
3174:
2355:
1521:, and relates bounded pathwidth with the existence of a
693:. And in the other direction, from a linear ordering of
512:
as a subgraph. That is, for every path decomposition of
3634:
Coudert, David; Huc, Florian; Mazauric, Dorian (2012),
3059:
Proc. 22nd ACM Symp. on Theory of Computing (STOC 1990)
375:
is the minimum width of any path-decomposition of
170:
of dynamic programming algorithms on graphs of bounded
56:. More formally, a path-decomposition is a sequence of
3504:
3452:
3001:
2617:
1934:
can be embedded into a three-dimensional grid of size
570:
is a subgraph of an interval graph with clique number
443:, and in the other direction one may recover the sets
242:
such that both endpoints of the edge belong to subset
5173:
5062:
Proc. 8th European Symposium on Algorithms (ESA 2000)
4927:
Discrete Mathematics and Theoretical Computer Science
4494:
4415:
Proc. International Symposium on Circuits and Systems
3908:
3895:
3588:
2855:
2836:
2309:
2280:
719:
670:
272:
4575:, vol. 726, Springer-Verlag, pp. 260–271,
1623:
The forbidden minors for graphs of pathwidth 1.
1614:
4920:"Classes of graphs with restricted interval models"
4411:
3553:
Proc. 2nd Scandinavian Workshop on Algorithm Theory
2227:
4597:
4465:
3933:
3633:
2871:
2801:
2733:
2325:
1261:, and if so to find a path-decomposition of width
881:. The pathwidth is also less than or equal to the
531:In one direction, suppose a path decomposition of
314:
5010:(2004), "Graph Minors. XX. Wagner's conjecture",
4917:
3865:
3546:
3259:
3045:
3029:
2986:
2602:
2543:
2399:
2267:
2265:
2263:
1015:are adjacent when the corresponding two edges of
199:In the first of their famous series of papers on
5201:
5002:
4970:
4938:
4844:
3902:
3663:
3093:
2816:
2709:
2575:
2559:
2212:
2208:
2206:
2181:
1518:
1283:, impractical except for the smallest values of
1205:
713:The node searching game on a graph is a form of
393:
212:
121:structure theory for minor-closed graph families
4946:(1983), "Graph minors. I. Excluding a forest",
4918:Proskurowski, Andrzej; Telle, Jan Arne (1999),
4523:
3988:Proc. 21st ACM Symposium on Theory of Computing
3977:
3470:
3384:
2922:
2847:
2845:
2760:
2555:
2336:
2334:
2275:
1564:does not include at least one forest, then the
1415:
1244:
1127:
315:{\displaystyle X_{i}\cap X_{k}\subseteq X_{j}.}
111:: the families of graphs that are closed under
3360:-arboretum of graphs with bounded treewidth",
3156:SIAM Journal on Algebraic and Discrete Methods
2884:Demaine, Hajiaghayi & Kawarabayashi (2005)
2260:
669:. The vertex separation number was defined by
5108:
4783:"The Magical Number Seven, Plus or Minus Two"
4428:(Ph.D. thesis), Washington State University,
4189:
3793:
2789:
2690:
2571:
2203:
1549:has bounded pathwidth if and only if the set
1367:, for the complements of chordal graphs, for
1133:What is the largest possible pathwidth of an
551:of the intervals formed from the vertices of
4355:
4023:
3414:Graph-Theoretic Concepts in Computer Science
3217:, New York: Academic Press, pp. 155–165
2938:
2842:
2632:
2331:
1635:has a path-decomposition with width at most
1509:as minors. In many cases, the properties of
1301:
661:is the smallest vertex separation number of
4890:
4651:
4305:
3716:
3303:
2495:
2479:
2443:
2427:
2411:
2313:
2297:
2295:
2162:
1985:in this DAG represents the fact that value
1631:is, itself, closed under taking minors: if
1386:
620:
192:
4676:
4440:
4423:
4060:
3352:
3316:
3290:
3213:(1967), "Some classes of perfect graphs",
2859:
2851:
2531:
2519:
2483:
2447:
2431:
2415:
2387:
2383:
2379:
2367:
2286:
2271:
2240:Arnborg, Corneil & Proskurowski (1987)
2197:
2193:
2033:
1831:Gate matrix layout is a specific style of
1604:-minor-free graphs have pathwidth at most
1306:
1295:
399:
379:. The subtraction of one from the size of
5189:
5138:"Pathwidth and layered drawings of trees"
5044:
5034:
5025:
5013:Journal of Combinatorial Theory, Series B
4993:
4981:Journal of Combinatorial Theory, Series B
4961:
4949:Journal of Combinatorial Theory, Series B
4872:IEEE Transactions on Circuits and Systems
4860:
4808:
4692:
4667:
4545:
4514:
4499:(1985), "Interval graphs and searching",
4485:
4456:
4402:
4390:Journal of Combinatorial Theory, Series B
4346:
4321:
4180:
4133:
4041:
3996:
3924:
3736:
3608:
3569:
3527:
3495:
3433:
3375:
3343:
3250:
3238:Journal of Combinatorial Theory, Series B
3066:
2666:
2451:
2305:
2043:
2036:describe an application of path-width in
1627:The property of having pathwidth at most
215:) define a path-decomposition of a graph
5135:
5087:
5058:
5037:Topics in Combinatorics and Graph Theory
4732:
4701:
4239:
4064:Algorithms for Graphs of Small Treewidth
3697:Combinatorics, Probability and Computing
2997:
2995:
2962:
2907:
2613:
2611:
2507:
2356:Aspvall, Proskurowski & Telle (2000)
2351:
2349:
2321:
2317:
2292:
2250:
2248:
2235:
2060:is given, with vertex separation number
1618:
1321:is restricted to bounded-degree graphs,
730:
708:
471:
181:
146:: testing whether a graph has pathwidth
107:. They play a key role in the theory of
4825:
4386:
4330:
3693:
3116:
2950:
2934:
2918:
2916:
2832:
2812:
2810:
2764:
2744:
2742:
2721:
2705:
2703:
2701:
2699:
2662:
2660:
2658:
2656:
2628:
2626:
2598:
2596:
2340:
2301:
1815:then the graph formed from them is its
1145:(more unsolved problems in mathematics)
665:with respect to any linear ordering of
520:, and for every interval supergraph of
516:one can find an interval supergraph of
5202:
4777:
3235:(1991), "Quickly excluding a forest",
3013:
3002:Bodlaender, Gustedt & Telle (1998)
2968:
2643:
2641:
2618:Bodlaender, Kloks & Kratsch (1993)
2177:
2175:
2173:
2171:
1856:Pathwidth has several applications to
4735:IEEE Transactions on Electron Devices
4242:Discrete Mathematics and Applications
4212:
4102:
3589:Cattell, Kevin; Dinneen, Michael J.;
3209:
2992:
2895:
2856:Takahashi, Ueno & Kajitani (1994)
2837:Cattell, Dinneen & Fellows (1996)
2776:
2647:
2608:
2587:
2346:
2310:Ellis, Sudborough & Turner (1994)
2245:
2223:
2221:
1864:The minimal graphs that have a given
1643:, and any vertex can be removed from
1485:are the graphs that have neither the
1441:
862:-leaves each adjacent to a separator
854:-tree that can be partitioned into a
739:, a maximal graph with pathwidth one.
671:Ellis, Sudborough & Turner (1983)
524:one can find a path decomposition of
467:
4767:IEEE Journal of Solid-State Circuits
4268:
3215:Graph Theory and Theoretical Physics
3097:SIAM Journal on Discrete Mathematics
2913:
2807:
2739:
2696:
2653:
2623:
2593:
1411:
36:is, informally, a representation of
3721:(2005), "Graph minor hierarchies",
2944:
2638:
2168:
1758:
1325:, planar graphs of bounded degree,
790:-caterpillar, two special kinds of
720:Kirousis & Papadimitriou (1985)
681:is a subgraph of an interval graph
673:, and is equal to the pathwidth of
555:is an interval graph that contains
405:
13:
5039:, Physica-Verlag, pp. 613–620
2802:Feige, Hajiaghayi & Lee (2005)
2734:Kloks, Kratsch & Müller (1995)
2326:Coudert, Huc & Mazauric (2012)
2218:
1989:is one of the inputs to operation
1952:
1887:is a placement of the vertices of
1119:, and the comparability graphs of
889:of the vertices in a given graph.
581:has a path decomposition of width
14:
5231:
3666:"Pathwidth of outerplanar graphs"
3418:Lecture Notes in Computer Science
2987:Dujmović, Morin & Wood (2003)
2544:Alon, Seymour & Thomas (1990)
2228:Kashiwabara & Fujisawa (1979)
1615:Obstructions to bounded pathwidth
1576:. But a perfect binary tree with
705:that comes last in the ordering.
450:as the vertex sets of the graphs
3420:, vol. 570, pp. 1–12,
2872:Kinnersley & Langston (1994)
2576:Amini, Huc & Pérennes (2009)
2560:Coudert, Huc & Sereni (2007)
1963:high-level programming languages
1851:
625:The vertex separation number of
3030:Björklund & Husfeldt (2008)
3019:
3007:
2980:
2956:
2928:
2901:
2889:
2877:
2865:
2822:
2795:
2783:
2770:
2754:
2727:
2715:
2684:
2672:
2603:Bodlaender & Möhring (1990)
2581:
2565:
2549:
2537:
2525:
2513:
2501:
2489:
2473:
2454:gives a tighter upper bound of
2437:
2421:
2405:
2400:Proskurowski & Telle (1999)
2393:
2373:
2361:
1790:
1694:. However, the set of trees in
1421:
1226:-vertex graphs are of the form
1128:Unsolved problem in mathematics
4810:11858/00-001M-0000-002C-4646-B
4444:Information Processing Letters
4137:Information Processing Letters
3903:Monien & Sudborough (1988)
3596:Information Processing Letters
2817:Robertson & Seymour (2004)
2710:Monien & Sudborough (1988)
2213:Robertson & Seymour (2003)
2187:
2182:Robertson & Seymour (1983)
2156:
2028:
1652:can be characterized by a set
1557:includes at least one forest.
1545:. Then, a minor-closed family
1519:Robertson & Seymour (1983)
1000:has a vertex for each edge of
653:in the ordering but that have
1:
5102:10.1016/S0196-6774(02)00225-0
4995:10.1016/S0095-8956(03)00042-X
4424:Kinnersley, Nancy G. (1989),
4404:10.1016/S0095-8956(03)00037-6
3402:10.1016/S0196-6774(02)00001-9
3377:10.1016/S0304-3975(97)00228-4
3038:
2923:Fellows & Langston (1989)
2761:Kloks & Bodlaender (1992)
2556:Bodlaender & Fomin (2002)
2276:Bodlaender & Kloks (1996)
1434:is another graph formed from
1416:Kloks & Bodlaender (1992)
1206:Computing path-decompositions
747:-vertex graph with pathwidth
585:whose nodes are given by the
394:Alternative characterizations
341:in which the underlying tree
177:
5191:10.1016/0012-365X(94)90092-2
5119:10.1007/978-3-540-74839-7_25
5049:; Fiedler, Miroslav (eds.),
4963:10.1016/0095-8956(83)90079-5
4862:10.1016/0304-3975(88)90028-X
4848:Theoretical Computer Science
4694:10.1016/0166-218X(92)90208-R
4680:Discrete Applied Mathematics
4669:10.1016/0166-218X(93)90171-J
4655:Discrete Applied Mathematics
4516:10.1016/0012-365X(85)90046-9
4487:10.1016/0166-218X(94)90021-3
4473:Discrete Applied Mathematics
4458:10.1016/0020-0190(92)90234-M
4348:10.1016/0166-218X(93)90012-D
4334:Discrete Applied Mathematics
4061:de Fluiter, Babette (1997),
3724:Discrete Applied Mathematics
3619:10.1016/0020-0190(95)00190-5
3363:Theoretical Computer Science
3252:10.1016/0095-8956(91)90068-U
1738:can be shown to be at least
1245:Fixed-parameter tractability
219:to be a sequence of subsets
7:
4765:, Also in the joint issue,
3912:Information and Computation
2790:Suchan & Todinca (2007)
2691:Downey & Fellows (1999)
2572:Fomin & Thilikos (2007)
2107:
2038:natural language processing
1971:placed in machine registers
1676:are forests: for instance,
1533:if there exists a constant
826:-tree that is not itself a
641:such that, for each vertex
566:In the other direction, if
500:The pathwidth of any graph
10:
5236:
5136:Suderman, Matthew (2004),
5027:10.1016/j.jctb.2004.08.001
4828:Computational Graph Theory
4497:Papadimitriou, Christos H.
4323:10.1016/j.disc.2007.01.020
2939:Ferreira & Song (1992)
2633:Habib & Möhring (1994)
1883:-layer drawing of a graph
1342:distance-hereditary graphs
649:vertices are earlier than
345:of the decomposition is a
5159:10.1142/S0218195904001433
4437:; see Theorem 6.A, p. 44.
4160:SIAM Journal on Computing
4150:10.1016/j.ipl.2005.10.012
4119:10.1007/s00373-002-0490-z
3939:Hajiaghayi, Mohammadtaghi
3851:10.1007/s00453-007-9151-1
3751:Hajiaghayi, MohammadTaghi
3738:10.1016/j.dam.2004.01.010
3710:10.1017/S0963548300001450
3657:10.1007/s00453-011-9524-3
3336:10.1137/S0097539793251219
3323:SIAM Journal on Computing
3276:10.1007/s00453-007-9149-8
2496:Gurski & Wanke (2007)
2480:Korach & Solel (1993)
2444:Korach & Solel (1993)
2428:Korach & Solel (1993)
2412:Korach & Solel (1993)
2163:Diestel & Kühn (2005)
1846:programmable logic arrays
1783:onto surfaces of bounded
1600:-vertex forest, then the
1537:such that every graph in
1460:Robertson–Seymour theorem
1317:remains NP-complete when
1302:Special classes of graphs
1273:. In the second phase, a
1251:fixed-parameter tractable
726:
144:fixed-parameter tractable
133:computational linguistics
5071:10.1007/3-540-45253-2_37
4902:10.1007/3-540-68535-9_32
4884:10.1109/TCS.1979.1084695
4608:10.1007/3-540-59071-4_41
4581:10.1007/3-540-57273-2_61
4538:10.1007/3-540-56279-6_64
4281:10.1109/SFCS.2000.892072
4254:10.1515/dma.1993.3.5.517
4223:10.1007/3-540-59071-4_35
4106:Graphs and Combinatorics
3803:Parameterized Complexity
3562:10.1007/3-540-52846-6_99
3520:10.1007/3-540-56939-1_66
2255:Bodlaender et al. (1992)
2150:
2034:Kornai & Tuza (1992)
1553:of forbidden minors for
1499:complete bipartite graph
1408:Bodlaender et al. (1992)
1387:Approximation algorithms
1329:, chordal dominoes, the
1029:planar separator theorem
939:, then the pathwidth of
621:Vertex separation number
252:For every three indices
90:vertex separation number
4755:10.1109/T-ED.1980.20086
4495:Kirousis, Lefteris M.;
4193:Journal of Graph Theory
3953:10.1145/1060590.1060674
3755:Kawarabayashi, Ken-ichi
3674:Journal of Graph Theory
3426:10.1007/3-540-55121-2_1
2829:Bienstock et al. (1991)
2667:Fomin & Høie (2006)
2466:on the pathwidth of an
1930:vertices and pathwidth
1795:
1775:can be decomposed into
1765:graph structure theorem
1237:for some constant
842:-tree with at most two
782:graph must be either a
637:is the smallest number
371:, and the pathwidth of
230:, with two properties:
115:and do not include all
4466:Kinnersley, Nancy G.;
3926:10.1006/inco.1994.1064
3488:10.1006/jagm.1996.0049
2975:Dujmović et al. (2008)
2908:Lopez & Law (1980)
2522:, Corollary 23, p. 10.
2102:minimum dominating set
2044:Exponential algorithms
1975:directed acyclic graph
1779:of graphs that can be
1624:
1588:, so in this case the
1541:has pathwidth at most
1513:and the properties of
1353:series–parallel graphs
964:series–parallel graphs
740:
497:
316:
196:
5090:Journal of Algorithms
3476:Journal of Algorithms
3390:Journal of Algorithms
3195:10.1007/s004530010025
3068:10.1145/100216.100254
2486:, Corollary 24, p.10.
2482:, Theorem 6, p. 100;
2450:, Theorem 66, p. 30.
2232:Ohtsuki et al. (1979)
2081:of these algorithms.
2001:For any fixed number
1842:Ohtsuki et al. (1979)
1808:Ohtsuki et al. (1979)
1622:
1584:levels has pathwidth
734:
709:Node searching number
475:
317:
185:
94:node searching number
5220:NP-complete problems
5177:Discrete Mathematics
4788:Psychological Review
4502:Discrete Mathematics
4468:Langston, Michael A.
4309:Discrete Mathematics
3991:, pp. 501–512,
3983:Langston, Michael A.
3947:, pp. 563–572,
3769:10.1109/SFCS.2005.14
3763:, pp. 637–646,
3061:, pp. 293–299,
2446:, Theorem 5, p. 99;
2434:, Theorem 49, p. 24.
2418:, Theorem 47, p. 24.
2370:, Theorem 29, p. 13.
1995:topological ordering
1659:of excluded minors.
1574:perfect binary trees
1335:comparability graphs
1117:comparability graphs
1004:and two vertices in
428:may be taken as the
270:
4747:1980ITED...27.1671L
4635:10.1007/11604686_34
4526:Bodlaender, Hans L.
3998:10.1145/73007.73055
3979:Fellows, Michael R.
3805:, Springer-Verlag,
3799:Fellows, Michael R.
3717:Diestel, Reinhard;
3591:Fellows, Michael R.
3548:Bodlaender, Hans L.
3506:Bodlaender, Hans L.
3472:Bodlaender, Hans L.
3454:Bodlaender, Hans L.
3410:Bodlaender, Hans L.
3386:Bodlaender, Hans L.
3356:(1998), "A partial
3354:Bodlaender, Hans L.
3318:Bodlaender, Hans L.
3292:Bodlaender, Hans L.
3179:-tree algorithms",
3026:Kneis et al. (2005)
2749:Kloks et al. (1993)
2679:Fomin et al. (2008)
2534:, Theorem 20, p. 9.
2050:dynamic programming
1746:. The complete set
1473:is a finite set of
1393:approximation ratio
1377:circular-arc graphs
1275:dynamic programming
1253:: for any constant
858:-path and a set of
633:of the vertices of
164:dynamic programming
105:tree decompositions
73:(one less than the
5210:Graph minor theory
5047:Nešetřil, Jaroslav
4772:(4): 736–740, 1980
4718:10.1007/BF00264496
4418:, pp. 657–660
4372:10.1007/BF01462229
4072:Utrecht University
4034:10.1007/BFb0023825
3465:, pp. 574–583
3131:10.1007/BF01934985
2430:, Lemma 1, p. 99;
2314:Peng et al. (1998)
1907:. Therefore, when
1625:
1529:of graphs to have
1442:Excluding a forest
1369:permutation graphs
1357:outerplanar graphs
1109:permutation graphs
960:outerplanar graphs
850:-caterpillar is a
815:, each containing
741:
629:with respect to a
549:intersection graph
498:
468:Interval thickness
328:tree decomposition
312:
238:, there exists an
205:Neil Robertson
197:
193:Bodlaender (1994a)
71:interval thickness
27:path decomposition
5128:978-3-540-74838-0
5080:978-3-540-41004-1
4911:978-3-540-64824-6
4779:Miller, George A.
4644:978-3-540-31000-6
4617:978-3-540-59071-2
4590:978-3-540-57273-2
4557:978-3-540-56279-5
4316:(22): 2734–2754,
4232:978-3-540-59071-2
4206:10.1002/jgt.20219
4173:10.1137/050643350
3687:10.1002/jgt.20218
3581:978-3-540-52846-3
3539:978-3-540-56939-8
3445:978-3-540-55121-8
3148:Corneil, Derek G.
3146:Arnborg, Stefan;
3110:10.1137/060670146
2860:Bodlaender (1998)
2852:Kinnersley (1992)
2532:Bodlaender (1998)
2520:Bodlaender (1998)
2484:Bodlaender (1998)
2448:Bodlaender (1998)
2432:Bodlaender (1998)
2416:Bodlaender (1998)
2388:Bodlaender (1998)
2384:Kinnersley (1992)
2380:Kinnersley (1989)
2368:Bodlaender (1998)
2287:Bodlaender (1994)
2272:Bodlaender (1996)
2198:Bodlaender (1998)
2194:Kinnersley (1989)
2092:/6 + o(
1531:bounded pathwidth
1363:, as well as for
1307:Bodlaender (1994)
1296:de Fluiter (1997)
1031:to find a set of
985:; the line graph
872:caterpillar trees
430:induced subgraphs
400:Bodlaender (1998)
390:be equal to one.
234:For each edge of
195:, emphasis added)
186:An example graph
40:as a "thickened"
5227:
5215:Graph invariants
5194:
5193:
5184:(1–3): 293–304,
5169:
5167:
5161:, archived from
5142:
5131:
5104:
5083:
5054:
5040:
5030:
5029:
5008:Seymour, Paul D.
4998:
4997:
4966:
4965:
4934:
4924:
4914:
4886:
4865:
4864:
4855:(1–3): 209–229,
4840:
4821:
4812:
4801:10.1037/h0043158
4773:
4741:(8): 1671–1675,
4728:
4705:Acta Informatica
4697:
4696:
4672:
4671:
4647:
4620:
4593:
4560:
4549:
4519:
4518:
4490:
4489:
4480:(2–3): 169–213,
4461:
4460:
4436:
4419:
4407:
4406:
4382:
4351:
4350:
4326:
4325:
4301:
4264:
4235:
4208:
4185:
4184:
4167:(3): 1058–1079,
4152:
4129:
4098:
4097:
4096:
4090:
4084:, archived from
4070:, Ph.D. thesis,
4069:
4056:
4045:
4019:
4000:
3973:
3929:
3928:
3900:
3891:
3883:
3861:
3815:
3789:
3747:Demaine, Erik D.
3741:
3740:
3712:
3689:
3670:
3659:
3640:
3629:
3612:
3584:
3573:
3542:
3531:
3500:
3499:
3466:
3464:
3448:
3437:
3404:
3380:
3379:
3348:
3347:
3330:(6): 1305–1317,
3313:
3306:Acta Cybernetica
3299:
3286:
3255:
3254:
3223:Bienstock, Dan;
3218:
3205:
3170:
3153:
3141:
3112:
3104:(3): 1311–1316,
3089:
3070:
3033:
3023:
3017:
3011:
3005:
2999:
2990:
2984:
2978:
2972:
2966:
2960:
2954:
2948:
2942:
2932:
2926:
2920:
2911:
2905:
2899:
2893:
2887:
2881:
2875:
2869:
2863:
2849:
2840:
2826:
2820:
2814:
2805:
2799:
2793:
2787:
2781:
2774:
2768:
2758:
2752:
2746:
2737:
2731:
2725:
2719:
2713:
2707:
2694:
2688:
2682:
2676:
2670:
2664:
2651:
2645:
2636:
2630:
2621:
2615:
2606:
2600:
2591:
2585:
2579:
2569:
2563:
2553:
2547:
2541:
2535:
2529:
2523:
2517:
2511:
2505:
2499:
2493:
2487:
2477:
2471:
2469:
2465:
2452:Scheffler (1992)
2441:
2435:
2425:
2419:
2414:, Lemma 3 p.99;
2409:
2403:
2397:
2391:
2377:
2371:
2365:
2359:
2353:
2344:
2338:
2329:
2306:Scheffler (1990)
2299:
2290:
2284:
2278:
2269:
2258:
2252:
2243:
2225:
2216:
2210:
2201:
2191:
2185:
2179:
2166:
2160:
2086:exponential time
2079:space complexity
2075:
1947:
1835:VLSI layout for
1774:
1771:, the graphs in
1770:
1759:Structure theory
1754:
1745:
1737:
1730:
1721:
1712:
1700:
1693:
1684:
1675:
1668:
1658:
1651:
1646:
1642:
1638:
1634:
1630:
1610:
1603:
1599:
1595:
1591:
1587:
1583:
1571:
1567:
1563:
1556:
1552:
1548:
1544:
1540:
1536:
1528:
1516:
1512:
1508:
1496:
1481:states that the
1479:Wagner's theorem
1477:. For instance,
1475:forbidden minors
1472:
1468:
1464:
1457:
1453:
1449:
1437:
1433:
1405:
1320:
1316:
1312:
1293:
1286:
1282:
1272:
1268:
1264:
1260:
1256:
1240:
1236:
1225:
1221:
1217:
1201:
1200:
1199:
1195:
1183:
1176:
1172:
1166:
1165:
1161:
1136:
1129:
1094:
1092:
1091:
1078:
1076:
1075:
1061:
1060:
1059:
1055:
1046:
1044:
1043:
1018:
1014:
1003:
999:
995:
957:
942:
938:
934:
930:
925:
924:
923:
919:
910:
895:
869:
865:
861:
857:
853:
849:
845:
841:
837:
833:
825:
821:
811:
797:
793:
789:
785:
781:
777:
769:
750:
746:
737:caterpillar tree
704:
700:
696:
692:
688:
684:
680:
676:
668:
664:
660:
656:
652:
648:
644:
640:
636:
628:
608:
604:
600:
596:
592:
584:
580:
576:
569:
562:
558:
554:
546:
542:
538:
534:
527:
523:
519:
515:
511:
503:
495:
491:
487:
483:
463:
456:
449:
442:
438:
427:
420:
416:
406:Gluing sequences
385:
378:
374:
370:
368:
344:
340:
321:
319:
318:
313:
308:
307:
295:
294:
282:
281:
265:
248:
241:
237:
229:
225:
218:
189:
168:space complexity
161:
153:
149:
87:
67:
55:
51:
39:
35:
5235:
5234:
5230:
5229:
5228:
5226:
5225:
5224:
5200:
5199:
5198:
5165:
5140:
5129:
5081:
5004:Robertson, Neil
4972:Robertson, Neil
4940:Robertson, Neil
4922:
4912:
4838:
4645:
4618:
4591:
4558:
4291:
4275:, p. 126,
4233:
4094:
4092:
4088:
4082:
4067:
4054:
4009:
3963:
3881:
3813:
3779:
3668:
3638:
3582:
3540:
3462:
3446:
3225:Robertson, Neil
3168:10.1137/0608024
3151:
3079:
3041:
3036:
3024:
3020:
3012:
3008:
3000:
2993:
2985:
2981:
2973:
2969:
2963:Suderman (2004)
2961:
2957:
2949:
2945:
2933:
2929:
2921:
2914:
2906:
2902:
2894:
2890:
2882:
2878:
2870:
2866:
2850:
2843:
2827:
2823:
2815:
2808:
2800:
2796:
2788:
2784:
2775:
2771:
2759:
2755:
2747:
2740:
2732:
2728:
2720:
2716:
2708:
2697:
2689:
2685:
2677:
2673:
2665:
2654:
2646:
2639:
2631:
2624:
2616:
2609:
2601:
2594:
2586:
2582:
2570:
2566:
2554:
2550:
2542:
2538:
2530:
2526:
2518:
2514:
2508:Golovach (1993)
2506:
2502:
2494:
2490:
2478:
2474:
2470:-vertex forest.
2467:
2459:
2455:
2442:
2438:
2426:
2422:
2410:
2406:
2398:
2394:
2378:
2374:
2366:
2362:
2354:
2347:
2339:
2332:
2322:Skodinis (2003)
2318:Skodinis (2000)
2300:
2293:
2285:
2281:
2270:
2261:
2253:
2246:
2236:Lengauer (1981)
2226:
2219:
2211:
2204:
2192:
2188:
2180:
2169:
2161:
2157:
2153:
2144:Strahler number
2138:Graph bandwidth
2110:
2069:
2046:
2031:
1955:
1953:Compiler design
1935:
1923:-layer drawing.
1866:crossing number
1854:
1798:
1793:
1772:
1768:
1761:
1753:
1747:
1739:
1736:
1732:
1729:
1723:
1720:
1714:
1711:
1702:
1699:
1695:
1692:
1686:
1683:
1677:
1674:
1670:
1667:
1663:
1657:
1653:
1649:
1644:
1640:
1636:
1632:
1628:
1617:
1605:
1601:
1597:
1593:
1589:
1585:
1577:
1569:
1565:
1561:
1554:
1550:
1546:
1542:
1538:
1534:
1526:
1514:
1510:
1507:
1501:
1495:
1489:
1470:
1466:
1462:
1458:), then by the
1455:
1451:
1447:
1444:
1435:
1431:
1424:
1396:
1389:
1381:interval graphs
1318:
1314:
1310:
1304:
1288:
1287:. For the case
1284:
1278:
1270:
1266:
1262:
1258:
1254:
1247:
1238:
1227:
1223:
1219:
1215:
1208:
1197:
1191:
1190:
1189:
1178:
1174:
1163:
1157:
1156:
1155:
1148:
1147:
1142:
1134:
1131:
1121:interval orders
1087:
1085:
1080:
1071:
1069:
1064:
1057:
1050:
1049:
1048:
1039:
1037:
1032:
1016:
1005:
1001:
997:
986:
944:
940:
936:
932:
928:
921:
914:
913:
912:
901:
893:
867:
866:-clique of the
863:
859:
855:
851:
847:
846:-leaves, and a
843:
839:
835:
827:
823:
822:vertices; in a
816:
813:maximal cliques
803:
795:
791:
787:
783:
779:
775:
770:edges, and the
752:
748:
744:
729:
715:pursuit–evasion
711:
702:
698:
694:
690:
686:
682:
678:
674:
666:
662:
658:
654:
650:
646:
642:
638:
634:
631:linear ordering
626:
623:
606:
602:
598:
594:
590:
587:maximal cliques
582:
578:
571:
567:
560:
556:
552:
544:
540:
536:
532:
525:
521:
517:
513:
509:
501:
493:
489:
485:
481:
470:
462:
458:
455:
451:
448:
444:
440:
437:
433:
426:
422:
418:
415:
411:
408:
396:
384:
380:
376:
372:
366:
361:
359:
353:
342:
330:
303:
299:
290:
286:
277:
273:
271:
268:
267:
253:
247:
243:
239:
235:
227:
226:of vertices of
224:
220:
216:
187:
180:
159:
151:
147:
85:
65:
53:
49:
37:
33:
17:
12:
11:
5:
5233:
5223:
5222:
5217:
5212:
5197:
5196:
5171:
5153:(3): 203–225,
5133:
5127:
5106:
5085:
5079:
5056:
5042:
5032:
5020:(2): 325–357,
5000:
4968:
4936:
4915:
4910:
4888:
4878:(9): 675–684,
4867:
4842:
4836:
4823:
4775:
4730:
4712:(4): 465–475,
4699:
4674:
4649:
4643:
4622:
4616:
4595:
4589:
4567:Bodlaender, H.
4562:
4556:
4521:
4509:(2): 181–184,
4492:
4463:
4451:(6): 345–350,
4438:
4421:
4409:
4397:(2): 347–367,
4384:
4353:
4341:(3): 233–248,
4328:
4303:
4289:
4266:
4248:(5): 517–522,
4237:
4231:
4210:
4187:
4154:
4144:(5): 191–196,
4131:
4100:
4080:
4058:
4052:
4021:
4007:
3975:
3961:
3931:
3906:
3901:. As cited by
3893:
3875:Wood, David R.
3867:Dujmović, Vida
3863:
3845:(2): 267–292,
3833:Wood, David R.
3829:Whitesides, S.
3817:
3811:
3795:Downey, Rod G.
3791:
3777:
3743:
3731:(2): 167–182,
3714:
3691:
3661:
3651:(1): 158–190,
3631:
3603:(4): 197–203,
3586:
3580:
3544:
3538:
3502:
3482:(2): 358–402,
3468:
3450:
3444:
3406:
3396:(2): 190–200,
3382:
3350:
3314:
3301:
3288:
3270:(2): 226–249,
3257:
3245:(2): 274–283,
3220:
3207:
3189:(3): 382–394,
3172:
3162:(2): 277–284,
3143:
3114:
3091:
3077:
3042:
3040:
3037:
3035:
3034:
3018:
3006:
2991:
2979:
2967:
2955:
2951:Hliněny (2003)
2943:
2935:Möhring (1990)
2927:
2912:
2900:
2888:
2876:
2864:
2841:
2833:Diestel (1995)
2821:
2806:
2794:
2782:
2769:
2765:Gustedt (1993)
2753:
2738:
2726:
2722:Gustedt (1993)
2714:
2695:
2683:
2671:
2652:
2637:
2622:
2607:
2592:
2580:
2564:
2548:
2536:
2524:
2512:
2500:
2488:
2472:
2457:
2436:
2420:
2404:
2392:
2372:
2360:
2345:
2341:Arnborg (1985)
2330:
2302:Möhring (1990)
2291:
2279:
2259:
2244:
2217:
2202:
2186:
2167:
2154:
2152:
2149:
2148:
2147:
2141:
2135:
2129:
2123:
2117:
2109:
2106:
2056:-vertex graph
2045:
2042:
2030:
2027:
1954:
1951:
1950:
1949:
1924:
1873:
1869:
1853:
1850:
1826:perfect graphs
1797:
1794:
1792:
1789:
1760:
1757:
1751:
1734:
1727:
1718:
1706:
1697:
1690:
1681:
1672:
1665:
1655:
1616:
1613:
1505:
1493:
1487:complete graph
1443:
1440:
1423:
1420:
1388:
1385:
1327:chordal graphs
1303:
1300:
1246:
1243:
1207:
1204:
1143:
1132:
1126:
931:-vertex graph
900:has pathwidth
887:maximum degree
728:
725:
710:
707:
622:
619:
508:that contains
506:interval graph
478:interval graph
469:
466:
460:
453:
446:
435:
424:
413:
407:
404:
395:
392:
382:
364:
355:
323:
322:
311:
306:
302:
298:
293:
289:
285:
280:
276:
250:
245:
222:
179:
176:
75:maximum clique
15:
9:
6:
4:
3:
2:
5232:
5221:
5218:
5216:
5213:
5211:
5208:
5207:
5205:
5192:
5187:
5183:
5179:
5178:
5172:
5168:on 2003-05-03
5164:
5160:
5156:
5152:
5148:
5147:
5139:
5134:
5130:
5124:
5120:
5116:
5112:
5107:
5103:
5099:
5095:
5091:
5086:
5082:
5076:
5072:
5068:
5064:
5063:
5057:
5052:
5048:
5043:
5038:
5033:
5028:
5023:
5019:
5015:
5014:
5009:
5005:
5001:
4996:
4991:
4987:
4983:
4982:
4977:
4976:Seymour, Paul
4973:
4969:
4964:
4959:
4955:
4951:
4950:
4945:
4944:Seymour, Paul
4941:
4937:
4932:
4928:
4921:
4916:
4913:
4907:
4903:
4899:
4895:
4889:
4885:
4881:
4877:
4873:
4868:
4863:
4858:
4854:
4850:
4849:
4843:
4839:
4837:3-211-82177-5
4833:
4829:
4824:
4820:
4816:
4811:
4806:
4802:
4798:
4794:
4790:
4789:
4784:
4780:
4776:
4771:
4768:
4764:
4760:
4756:
4752:
4748:
4744:
4740:
4736:
4731:
4727:
4723:
4719:
4715:
4711:
4707:
4706:
4700:
4695:
4690:
4686:
4682:
4681:
4675:
4670:
4665:
4662:(1): 97–101,
4661:
4657:
4656:
4650:
4646:
4640:
4636:
4632:
4628:
4623:
4619:
4613:
4609:
4605:
4601:
4596:
4592:
4586:
4582:
4578:
4574:
4573:
4568:
4563:
4559:
4553:
4548:
4543:
4539:
4535:
4531:
4527:
4522:
4517:
4512:
4508:
4504:
4503:
4498:
4493:
4488:
4483:
4479:
4475:
4474:
4469:
4464:
4459:
4454:
4450:
4446:
4445:
4439:
4435:
4431:
4427:
4422:
4417:
4416:
4410:
4405:
4400:
4396:
4392:
4391:
4385:
4381:
4377:
4373:
4369:
4365:
4361:
4360:
4354:
4349:
4344:
4340:
4336:
4335:
4329:
4324:
4319:
4315:
4311:
4310:
4304:
4300:
4296:
4292:
4290:0-7695-0850-2
4286:
4282:
4278:
4274:
4273:
4267:
4263:
4259:
4255:
4251:
4247:
4243:
4238:
4234:
4228:
4224:
4220:
4216:
4211:
4207:
4203:
4199:
4195:
4194:
4188:
4183:
4178:
4174:
4170:
4166:
4162:
4161:
4155:
4151:
4147:
4143:
4139:
4138:
4132:
4128:
4124:
4120:
4116:
4112:
4108:
4107:
4101:
4091:on 2011-07-24
4087:
4083:
4081:90-393-1528-0
4077:
4073:
4066:
4065:
4059:
4055:
4053:3-540-55284-7
4049:
4044:
4039:
4035:
4031:
4027:
4022:
4018:
4014:
4010:
4004:
3999:
3994:
3990:
3989:
3984:
3980:
3976:
3972:
3968:
3964:
3958:
3954:
3950:
3946:
3945:
3940:
3936:
3932:
3927:
3922:
3918:
3914:
3913:
3907:
3904:
3899:
3894:
3889:
3888:
3880:
3876:
3872:
3868:
3864:
3860:
3856:
3852:
3848:
3844:
3840:
3839:
3834:
3830:
3826:
3825:Fellows, M.R.
3822:
3818:
3814:
3812:0-387-94883-X
3808:
3804:
3800:
3796:
3792:
3788:
3784:
3780:
3778:0-7695-2468-0
3774:
3770:
3766:
3762:
3761:
3756:
3752:
3748:
3744:
3739:
3734:
3730:
3726:
3725:
3720:
3719:Kühn, Daniela
3715:
3711:
3707:
3703:
3699:
3698:
3692:
3688:
3684:
3680:
3676:
3675:
3667:
3662:
3658:
3654:
3650:
3646:
3645:
3637:
3632:
3628:
3624:
3620:
3616:
3611:
3606:
3602:
3598:
3597:
3592:
3587:
3583:
3577:
3572:
3567:
3563:
3559:
3555:
3554:
3549:
3545:
3541:
3535:
3530:
3525:
3521:
3517:
3513:
3512:
3507:
3503:
3498:
3493:
3489:
3485:
3481:
3477:
3473:
3469:
3461:
3460:
3455:
3451:
3447:
3441:
3436:
3431:
3427:
3423:
3419:
3415:
3411:
3407:
3403:
3399:
3395:
3391:
3387:
3383:
3378:
3373:
3370:(1–2): 1–45,
3369:
3365:
3364:
3359:
3355:
3351:
3346:
3341:
3337:
3333:
3329:
3325:
3324:
3319:
3315:
3311:
3307:
3302:
3297:
3293:
3289:
3285:
3281:
3277:
3273:
3269:
3265:
3264:
3258:
3253:
3248:
3244:
3240:
3239:
3234:
3233:Thomas, Robin
3230:
3229:Seymour, Paul
3226:
3221:
3216:
3212:
3211:Berge, Claude
3208:
3204:
3200:
3196:
3192:
3188:
3184:
3183:
3178:
3173:
3169:
3165:
3161:
3157:
3149:
3144:
3140:
3136:
3132:
3128:
3124:
3120:
3115:
3111:
3107:
3103:
3099:
3098:
3092:
3088:
3084:
3080:
3074:
3069:
3064:
3060:
3056:
3055:Thomas, Robin
3052:
3051:Seymour, Paul
3048:
3044:
3043:
3031:
3027:
3022:
3015:
3014:Miller (1956)
3010:
3003:
2998:
2996:
2988:
2983:
2976:
2971:
2964:
2959:
2952:
2947:
2940:
2936:
2931:
2924:
2919:
2917:
2909:
2904:
2897:
2892:
2885:
2880:
2873:
2868:
2861:
2857:
2853:
2848:
2846:
2838:
2834:
2830:
2825:
2818:
2813:
2811:
2803:
2798:
2791:
2786:
2778:
2773:
2766:
2762:
2757:
2750:
2745:
2743:
2735:
2730:
2723:
2718:
2711:
2706:
2704:
2702:
2700:
2692:
2687:
2680:
2675:
2668:
2663:
2661:
2659:
2657:
2649:
2644:
2642:
2634:
2629:
2627:
2619:
2614:
2612:
2604:
2599:
2597:
2589:
2584:
2577:
2573:
2568:
2561:
2557:
2552:
2545:
2540:
2533:
2528:
2521:
2516:
2509:
2504:
2497:
2492:
2485:
2481:
2476:
2463:
2453:
2449:
2445:
2440:
2433:
2429:
2424:
2417:
2413:
2408:
2401:
2396:
2390:, Theorem 51.
2389:
2385:
2381:
2376:
2369:
2364:
2357:
2352:
2350:
2342:
2337:
2335:
2327:
2323:
2319:
2315:
2311:
2307:
2303:
2298:
2296:
2288:
2283:
2277:
2273:
2268:
2266:
2264:
2256:
2251:
2249:
2241:
2237:
2233:
2229:
2224:
2222:
2214:
2209:
2207:
2199:
2195:
2190:
2183:
2178:
2176:
2174:
2172:
2164:
2159:
2155:
2145:
2142:
2139:
2136:
2133:
2130:
2127:
2124:
2121:
2118:
2115:
2112:
2111:
2105:
2103:
2099:
2095:
2091:
2087:
2082:
2080:
2073:
2067:
2063:
2059:
2055:
2051:
2041:
2039:
2035:
2026:
2024:
2020:
2016:
2012:
2008:
2004:
1999:
1996:
1992:
1988:
1984:
1980:
1976:
1972:
1968:
1964:
1960:
1946:
1942:
1938:
1933:
1929:
1926:A graph with
1925:
1922:
1918:
1914:
1910:
1906:
1902:
1898:
1894:
1890:
1886:
1882:
1878:
1874:
1870:
1867:
1863:
1862:
1861:
1859:
1858:graph drawing
1852:Graph drawing
1849:
1847:
1843:
1838:
1837:Boolean logic
1834:
1829:
1827:
1822:
1818:
1814:
1809:
1805:
1803:
1788:
1786:
1782:
1778:
1766:
1756:
1750:
1743:
1726:
1717:
1709:
1705:
1689:
1680:
1660:
1621:
1612:
1608:
1581:
1575:
1558:
1532:
1524:
1520:
1504:
1500:
1492:
1488:
1484:
1483:planar graphs
1480:
1476:
1461:
1439:
1429:
1419:
1417:
1413:
1409:
1403:
1399:
1394:
1384:
1382:
1378:
1374:
1370:
1366:
1362:
1358:
1354:
1349:
1347:
1346:circle graphs
1343:
1340:
1336:
1332:
1328:
1324:
1323:planar graphs
1308:
1299:
1297:
1291:
1281:
1276:
1252:
1249:Pathwidth is
1242:
1234:
1230:
1213:
1203:
1202:upper bound.
1194:
1187:
1182:
1170:
1160:
1153:
1146:
1140:
1124:
1122:
1118:
1114:
1110:
1106:
1101:
1098:
1090:
1083:
1074:
1067:
1054:
1042:
1035:
1030:
1026:
1021:
1012:
1008:
993:
989:
984:
980:
976:
971:
969:
965:
961:
955:
951:
947:
918:
908:
904:
899:
890:
888:
884:
880:
875:
873:
831:
819:
814:
810:
806:
802:with exactly
801:
800:chordal graph
773:
767:
763:
759:
755:
738:
733:
724:
721:
716:
706:
672:
632:
618:
615:
614:chordal graph
610:
588:
574:
564:
550:
529:
507:
479:
474:
465:
431:
421:. The graphs
403:
401:
391:
389:
367:
358:
350:
348:
338:
334:
329:
309:
304:
300:
296:
291:
287:
283:
278:
274:
264:
260:
256:
251:
233:
232:
231:
214:
210:
207: and
206:
202:
194:
184:
175:
173:
169:
165:
157:
145:
141:
136:
134:
130:
129:graph drawing
126:
122:
118:
114:
110:
106:
102:
97:
95:
91:
83:
80:
76:
72:
63:
59:
47:
43:
32:
28:
24:
19:
5181:
5175:
5163:the original
5150:
5144:
5110:
5096:(1): 40–59,
5093:
5089:
5061:
5050:
5036:
5017:
5011:
4988:(1): 43–76,
4985:
4979:
4956:(1): 39–61,
4953:
4947:
4930:
4926:
4893:
4875:
4871:
4852:
4846:
4827:
4795:(2): 81–97,
4792:
4786:
4769:
4766:
4738:
4734:
4709:
4703:
4687:(1): 87–92,
4684:
4678:
4659:
4653:
4626:
4599:
4571:
4529:
4524:Kloks, Ton;
4506:
4500:
4477:
4471:
4448:
4442:
4425:
4414:
4394:
4388:
4366:(1): 47–60,
4363:
4357:
4338:
4332:
4313:
4307:
4271:
4245:
4241:
4214:
4200:(1): 42–54,
4197:
4191:
4164:
4158:
4141:
4135:
4113:(1): 91–99,
4110:
4104:
4093:, retrieved
4086:the original
4063:
4025:
3987:
3943:
3935:Feige, Uriel
3919:(1): 50–79,
3916:
3910:
3897:
3886:
3842:
3838:Algorithmica
3836:
3821:Dujmović, V.
3802:
3759:
3728:
3722:
3704:(1): 27–30,
3701:
3695:
3681:(1): 27–41,
3678:
3672:
3648:
3644:Algorithmica
3642:
3610:math/9410211
3600:
3594:
3552:
3510:
3479:
3475:
3458:
3413:
3393:
3389:
3367:
3361:
3357:
3327:
3321:
3309:
3305:
3295:
3267:
3263:Algorithmica
3261:
3242:
3236:
3214:
3186:
3182:Algorithmica
3180:
3176:
3159:
3155:
3122:
3118:
3101:
3095:
3058:
3021:
3009:
2982:
2970:
2958:
2946:
2930:
2903:
2896:Berge (1967)
2891:
2879:
2867:
2824:
2797:
2785:
2777:Garbe (1995)
2772:
2756:
2729:
2717:
2686:
2674:
2648:Garbe (1995)
2588:Fomin (2003)
2583:
2567:
2551:
2539:
2527:
2515:
2503:
2491:
2475:
2461:
2439:
2423:
2407:
2395:
2375:
2363:
2282:
2189:
2158:
2093:
2089:
2083:
2071:
2065:
2061:
2057:
2053:
2047:
2032:
2022:
2018:
2014:
2010:
2006:
2002:
2000:
1990:
1986:
1982:
1978:
1967:control flow
1956:
1944:
1940:
1936:
1931:
1927:
1920:
1916:
1912:
1908:
1904:
1900:
1896:
1892:
1888:
1884:
1880:
1876:
1855:
1830:
1806:
1799:
1791:Applications
1762:
1748:
1741:
1724:
1715:
1707:
1703:
1687:
1678:
1661:
1626:
1606:
1596:contains an
1579:
1559:
1530:
1502:
1490:
1446:If a family
1445:
1425:
1422:Graph minors
1401:
1397:
1390:
1365:split graphs
1361:Halin graphs
1350:
1305:
1289:
1279:
1248:
1232:
1228:
1209:
1192:
1180:
1168:
1158:
1149:
1102:
1088:
1081:
1072:
1065:
1052:
1040:
1033:
1025:planar graph
1022:
1010:
1006:
991:
987:
975:clique-width
972:
968:Halin graphs
953:
949:
945:
916:
906:
902:
891:
876:
829:
817:
808:
804:
765:
761:
757:
753:
751:has at most
742:
712:
624:
611:
572:
565:
530:
499:
432:of the sets
409:
397:
362:
356:
351:
336:
332:
324:
262:
258:
254:
209:Paul Seymour
201:graph minors
198:
137:
113:graph minors
109:graph minors
98:
93:
89:
70:
45:
26:
23:graph theory
20:
18:
4565:Kloks, T.;
4043:10068/43314
3125:(1): 2–23,
2098:maximum cut
2029:Linguistics
1959:compilation
1777:clique-sums
1454:is also in
1430:of a graph
1412:Guha (2000)
1331:complements
1313:is at most
1212:NP-complete
1186:lower bound
1152:cubic graph
1139:cubic graph
1113:complements
996:of a graph
983:line graphs
838:-path is a
798:-tree is a
786:-path or a
77:size in an
5204:Categories
5053:, Elsevier
4547:1874/16672
4095:2010-05-06
4008:0897913078
3962:1581139608
3871:Morin, Pat
3571:1874/16625
3529:1874/16657
3497:1874/16538
3435:1874/17927
3345:1874/16670
3078:0897913612
3047:Alon, Noga
3039:References
2132:Degeneracy
2126:Tree-depth
1919:-crossing
1879:-crossing
1817:line graph
1813:hypergraph
1097:dual graph
774:pathwidth-
645:, at most
388:path graph
369:| − 1
347:path graph
178:Definition
82:supergraph
44:, and the
42:path graph
4933:: 167–176
4434:303738168
4262:120745961
4182:1956/1151
3139:122263659
1662:Although
1339:bipartite
879:treewidth
794:-tree. A
297:⊆
284:∩
172:treewidth
101:treewidth
46:pathwidth
4819:13310704
4781:(1956),
4763:64469353
4726:19415148
4430:ProQuest
4127:43123449
3971:14097859
3877:(2003),
3801:(1999),
3787:13238254
3284:37693881
3154:-tree",
3087:17521329
2120:Cutwidth
2114:Boxicity
2108:See also
2068:in time
1981:to node
1821:coloring
1781:embedded
1497:nor the
1469:, where
1373:cographs
1188:and the
1173:, where
1137:-vertex
1105:cographs
979:cutwidth
958:. Since
896:-vertex
883:cutwidth
127:design,
79:interval
62:vertices
4743:Bibcode
4380:2648030
4299:9854056
4017:1854173
3859:2298634
3627:2442557
3203:9690525
2862:, p. 8.
2693:, p.12.
1957:In the
1218:, when
1196:⁄
1162:⁄
1150:In any
1086:√
1070:√
1056:⁄
1038:√
1023:In any
920:⁄
772:maximal
768:− 1)/2)
577:, then
211: (
140:NP-hard
117:forests
58:subsets
5125:
5077:
4908:
4834:
4817:
4761:
4724:
4641:
4614:
4587:
4554:
4432:
4378:
4297:
4287:
4260:
4229:
4125:
4078:
4050:
4015:
4005:
3969:
3959:
3857:
3809:
3785:
3775:
3625:
3578:
3536:
3442:
3282:
3201:
3137:
3085:
3075:
1523:forest
1400:((log
1375:, for
1371:, for
1359:, and
1337:, and
1210:It is
1111:, the
981:, via
966:, and
898:forest
743:Every
727:Bounds
605:, and
547:. The
492:, and
360:|
138:It is
131:, and
5166:(PDF)
5141:(PDF)
4923:(PDF)
4759:S2CID
4722:S2CID
4376:S2CID
4359:Order
4295:S2CID
4258:S2CID
4123:S2CID
4089:(PDF)
4068:(PDF)
4013:S2CID
3967:S2CID
3882:(PDF)
3855:S2CID
3783:S2CID
3669:(PDF)
3639:(PDF)
3623:S2CID
3605:arXiv
3463:(PDF)
3312:: 1–2
3280:S2CID
3199:S2CID
3135:S2CID
3083:S2CID
2780:type.
2151:Notes
1891:onto
1872:tree.
1785:genus
1428:minor
1179:0.082
1063:size
905:(log
249:, and
156:trees
92:, or
31:graph
29:of a
5123:ISBN
5075:ISBN
4906:ISBN
4832:ISBN
4815:PMID
4639:ISBN
4612:ISBN
4585:ISBN
4552:ISBN
4285:ISBN
4227:ISBN
4076:ISBN
4048:ISBN
4003:ISBN
3957:ISBN
3807:ISBN
3773:ISBN
3576:ISBN
3534:ISBN
3440:ISBN
3073:ISBN
2464:+ 1)
2100:and
2070:O(2
1993:. A
1911:and
1903:and
1833:CMOS
1802:VLSI
1796:VLSI
1763:The
1410:and
1167:+ o(
977:and
952:log
892:Any
832:+ 1)
213:1983
125:VLSI
103:and
25:, a
5186:doi
5182:127
5155:doi
5115:doi
5098:doi
5067:doi
5022:doi
4990:doi
4958:doi
4898:doi
4880:doi
4857:doi
4805:hdl
4797:doi
4751:doi
4714:doi
4689:doi
4664:doi
4631:doi
4604:doi
4577:doi
4542:hdl
4534:doi
4511:doi
4482:doi
4453:doi
4399:doi
4368:doi
4343:doi
4318:doi
4314:307
4277:doi
4250:doi
4219:doi
4202:doi
4177:hdl
4169:doi
4146:doi
4115:doi
4038:hdl
4030:doi
3993:doi
3949:doi
3921:doi
3917:113
3847:doi
3765:doi
3733:doi
3729:145
3706:doi
3683:doi
3653:doi
3615:doi
3566:hdl
3558:doi
3524:hdl
3516:doi
3492:hdl
3484:doi
3430:hdl
3422:doi
3398:doi
3372:doi
3368:209
3340:hdl
3332:doi
3272:doi
3247:doi
3191:doi
3164:doi
3127:doi
3119:BIT
3106:doi
3063:doi
2456:log
1961:of
1800:In
1710:− 1
1609:− 2
1582:+ 1
1506:3,3
1333:of
1292:= 2
1115:of
943:is
935:is
820:+ 1
764:+ (
603:CDF
599:CDE
595:ACD
591:ABC
575:+ 1
494:CDF
490:CDE
486:ACD
482:ABC
476:An
398:As
354:max
88:),
84:of
64:of
60:of
48:of
21:In
5206::
5180:,
5151:14
5149:,
5143:,
5121:,
5094:47
5092:,
5073:,
5018:92
5016:,
5006:;
4986:89
4984:,
4974:;
4954:35
4952:,
4942:;
4929:,
4925:,
4904:,
4876:26
4874:,
4853:58
4851:,
4813:,
4803:,
4793:63
4791:,
4785:,
4770:15
4757:,
4749:,
4739:27
4737:,
4720:,
4710:16
4708:,
4685:36
4683:,
4660:43
4658:,
4637:,
4610:,
4583:,
4550:,
4540:,
4507:55
4505:,
4478:54
4476:,
4449:42
4447:,
4395:88
4393:,
4374:,
4364:11
4362:,
4339:45
4337:,
4312:,
4293:,
4283:,
4256:,
4244:,
4225:,
4198:55
4196:,
4175:,
4165:38
4163:,
4142:97
4140:,
4121:,
4111:19
4109:,
4074:,
4046:,
4036:,
4011:,
4001:,
3981:;
3965:,
3955:,
3937:;
3915:,
3884:,
3873:;
3869:;
3853:,
3843:52
3841:,
3831:;
3823:;
3797:;
3781:,
3771:,
3753:;
3749:;
3727:,
3700:,
3679:55
3677:,
3671:,
3649:63
3647:,
3641:,
3621:,
3613:,
3601:57
3599:,
3574:,
3564:,
3532:,
3522:,
3490:,
3480:21
3478:,
3438:,
3428:,
3416:,
3394:43
3392:,
3366:,
3338:,
3328:25
3326:,
3310:11
3308:,
3278:,
3268:52
3266:,
3243:52
3241:,
3231:;
3227:;
3197:,
3187:27
3185:,
3158:,
3133:,
3123:25
3121:,
3102:23
3100:,
3081:,
3071:,
3053:;
3049:;
3028:;
2994:^
2937:;
2915:^
2858:;
2854:;
2844:^
2835:;
2831:;
2809:^
2763:;
2741:^
2698:^
2655:^
2640:^
2625:^
2610:^
2595:^
2574:;
2558:;
2460:(2
2386:;
2382:;
2348:^
2333:^
2324:;
2320:;
2316:;
2312:;
2308:;
2304:;
2294:^
2274:;
2262:^
2247:^
2238:;
2234:;
2230:;
2220:^
2205:^
2196:;
2170:^
2074:).
1943:×
1939:×
1875:A
1860::
1848:.
1744:!)
1611:.
1426:A
1418:.
1404:))
1355:,
1348:.
1298:.
1231:(2
1123:.
1107:,
962:,
874:.
807:−
760:−
735:A
607:FG
601:,
597:,
593:,
563:.
488:,
484:,
464:.
349:.
266:,
261:≤
257:≤
203:,
174:.
135:.
96:.
5195:.
5188::
5170:.
5157::
5132:.
5117::
5105:.
5100::
5084:.
5069::
5055:.
5041:.
5031:.
5024::
4999:.
4992::
4967:.
4960::
4935:.
4931:3
4900::
4887:.
4882::
4866:.
4859::
4841:.
4822:.
4807::
4799::
4774:.
4753::
4745::
4729:.
4716::
4698:.
4691::
4673:.
4666::
4648:.
4633::
4621:.
4606::
4594:.
4579::
4561:.
4544::
4536::
4520:.
4513::
4491:.
4484::
4462:.
4455::
4420:.
4408:.
4401::
4383:.
4370::
4352:.
4345::
4327:.
4320::
4302:.
4279::
4265:.
4252::
4246:3
4236:.
4221::
4209:.
4204::
4186:.
4179::
4171::
4153:.
4148::
4130:.
4117::
4099:.
4057:.
4040::
4032::
4020:.
3995::
3974:.
3951::
3930:.
3923::
3905:.
3892:.
3862:.
3849::
3816:.
3790:.
3767::
3742:.
3735::
3713:.
3708::
3702:4
3690:.
3685::
3660:.
3655::
3630:.
3617::
3607::
3585:.
3568::
3560::
3543:.
3526::
3518::
3501:.
3494::
3486::
3467:.
3449:.
3432::
3424::
3405:.
3400::
3381:.
3374::
3358:k
3349:.
3342::
3334::
3300:.
3287:.
3274::
3256:.
3249::
3219:.
3206:.
3193::
3177:k
3171:.
3166::
3160:8
3152:k
3142:.
3129::
3113:.
3108::
3090:.
3065::
3032:.
3016:.
3004:.
2989:.
2977:.
2965:.
2953:.
2941:.
2925:.
2910:.
2898:.
2886:.
2874:.
2839:.
2819:.
2804:.
2792:.
2767:.
2751:.
2724:.
2712:.
2681:.
2669:.
2650:.
2635:.
2620:.
2605:.
2590:.
2578:.
2562:.
2546:.
2510:.
2498:.
2468:n
2462:n
2458:3
2402:.
2358:.
2343:.
2328:.
2289:.
2257:.
2242:.
2215:.
2200:.
2184:.
2165:.
2094:n
2090:n
2072:n
2066:G
2062:w
2058:G
2054:n
2023:w
2019:w
2015:w
2011:w
2007:w
2003:w
1991:y
1987:x
1983:y
1979:x
1945:n
1941:p
1937:p
1932:p
1928:n
1921:h
1917:k
1913:k
1909:h
1905:k
1901:h
1897:k
1893:h
1889:G
1885:G
1881:h
1877:k
1773:F
1769:F
1752:2
1749:X
1742:p
1740:(
1735:p
1733:X
1728:0
1725:X
1719:1
1716:X
1708:p
1704:X
1698:p
1696:X
1691:3
1688:K
1682:1
1679:X
1673:p
1671:X
1666:p
1664:X
1656:p
1654:X
1650:p
1645:G
1641:G
1637:p
1633:G
1629:p
1607:n
1602:X
1598:n
1594:X
1590:X
1586:k
1580:k
1578:2
1570:X
1566:X
1562:X
1555:F
1551:X
1547:F
1543:p
1539:F
1535:p
1527:F
1515:X
1511:F
1503:K
1494:5
1491:K
1471:X
1467:X
1463:F
1456:F
1452:F
1448:F
1436:G
1432:G
1402:n
1398:O
1319:G
1315:k
1311:G
1290:k
1285:k
1280:k
1271:k
1267:k
1263:k
1259:k
1255:k
1239:c
1235:)
1233:n
1229:O
1224:n
1220:k
1216:k
1198:6
1193:n
1181:n
1175:n
1171:)
1169:n
1164:6
1159:n
1141:?
1135:n
1130::
1093:)
1089:n
1084:(
1082:O
1077:)
1073:n
1068:(
1066:O
1058:3
1053:n
1051:2
1045:)
1041:n
1036:(
1034:O
1017:G
1013:)
1011:G
1009:(
1007:L
1002:G
998:G
994:)
992:G
990:(
988:L
956:)
954:n
950:t
948:(
946:O
941:G
937:t
933:G
929:n
922:3
917:n
915:2
909:)
907:n
903:O
894:n
868:k
864:k
860:k
856:k
852:k
848:k
844:k
840:k
836:k
830:k
828:(
824:k
818:k
809:k
805:n
796:k
792:k
788:k
784:k
780:k
776:k
766:k
762:k
758:n
756:(
754:k
749:k
745:n
703:v
699:v
695:G
691:I
687:I
683:I
679:G
675:G
667:G
663:G
659:G
655:v
651:v
647:s
643:v
639:s
635:G
627:G
583:p
579:G
573:p
568:G
561:G
557:G
553:G
545:v
541:v
537:v
533:G
526:G
522:G
518:G
514:G
510:G
502:G
496:.
461:i
459:G
454:i
452:G
447:i
445:X
441:G
436:i
434:X
425:i
423:G
419:G
414:i
412:G
383:i
381:X
377:G
373:G
365:i
363:X
357:i
343:T
339:)
337:T
335:,
333:X
331:(
310:.
305:j
301:X
292:k
288:X
279:i
275:X
263:k
259:j
255:i
246:i
244:X
240:i
236:G
228:G
223:i
221:X
217:G
188:G
160:k
152:k
148:k
86:G
66:G
54:G
50:G
38:G
34:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
