Cutwidth

Last updated February 26, 2024

In graph theory, the cutwidth of an undirected graph is the smallest integer $k$ with the following property: there is an ordering of the vertices of the graph, such that every cut obtained by partitioning the vertices into earlier and later subsets of the ordering is crossed by at most $k$ edges. That is, if the vertices are numbered $v_{1},v_{2},\dots v_{n}$ , then for every $\ell =1,2,\dots n-1$ , the number of edges $v_{i}v_{j}$ with $i\leq \ell$ and $j>\ell$ is at most $k$ .^[1]

Relation to other parameters

Cutwidth is related to several other width parameters of graphs. In particular, it is always at least as large as the treewidth or pathwidth of the same graph. However, it is at most the pathwidth multiplied by $O(\Delta )$ , or the treewidth multiplied by $O(\Delta \log n)$ where $\Delta$ is the maximum degree and $n$ is the number of vertices.^[3]^[4] If a family of graphs has bounded maximum degree, and its graphs do not contain subdivisions of complete binary trees of unbounded size, then the graphs in the family have bounded cutwidth.^[4] In subcubic graphs (graphs of maximum degree three), the cutwidth equals the pathwidth plus one.^[5]

The cutwidth is greater than or equal to the minimum bisection number of any graph. This is minimum possible number of edges from one side to another for a partition of the vertices into two subsets of equal size (or as near equal as possible). Any linear layout of a graph, achieving its optimal cutwidth, also provides a bisection with the same number of edges, obtained by partitioning the layout into its first and second halves. The cutwidth is less than or equal to the maximum degree multiplied by the graph bandwidth, the maximum number of steps separating the endpoints of any edge in a linear arrangement chosen to minimize this quantity.^[6] Unlike bandwidth, cutwidth is unchanged when edges are subdivided into paths of more than one edge. It is closely related to the "topological bandwidth", the minimum bandwidth that can be obtained by subdividing edges of a given graph. In particular, for any tree it is sandwiched between the topological bandwidth $b^{*}$ and a slightly larger number, $b^{*}+\log _{2}b^{*}+2$ .^[1]

Another parameter, defined similarly to cutwidth in terms of numbers of edges spanning cuts in a graph, is the carving width. However, instead of using a linear ordering of vertices and a linear sequence of cuts, as in cutwidth, carving width uses cuts derived from a hierarchical clustering of vertices, making it more closely related to treewidth or branchwidth and less similar to the other width parameters involving linear orderings such as pathwidth or bandwidth.^[7]

Cutwidth can be used to provide a lower bound on another parameter, the crossing number, arising in the study of graph drawings. The crossing number of a graph is the minimum number of pairs of edges that intersect, in any drawing of the graph in the plane where each vertex touches only the edges for which it is an endpoint. In graphs of bounded degree, the crossing number is always at least proportional to the square of the cutwidth. A more precise bound, applying to graphs where the degrees are not bounded, is:^[8]

\operatorname {crossings} (G)\geq {\frac {1}{1176}}\operatorname {cutwidth} (G)^{2}-\sum _{v\in V(G)}\left({\frac {\deg(v)}{4}}\right)^{2}.

Here, the correction term, proportional to the sum of squared degrees, is necessary to account for the existence of planar graphs whose squared cutwidth is proportional to this quantity but whose crossing number is zero.^[8] In another style of graph drawing, book embedding, vertices are arranged on a line and edges are arranged without crossings into separate half-plane pages meeting at this line. The page width of a book embedding has been defined as the largest cutwidth of any of the pages, using the same vertex ordering.^[9]

Computational complexity

The cutwidth can be found, and a linear layout of optimal width constructed, in time $O(n\log n)$ for a tree of $n$ vertices.^[10] For more general graphs, it is NP-hard. It remains NP-hard even for planar graphs of maximum degree three, and a weighted version of the problem (minimizing the weight of edges across any cut of a linear arrangement) is NP-hard even when the input is a tree.^[11]

Cutwidth is one of many problems of optimal linear arrangement that can be solved exactly in time $O(n2^{n})$ by the Held-Karp algorithm, using dynamic programming.^[12] A faster quantum algorithm with time $O(1.817^{n})$ is also known.^[13] Additionally, it is fixed-parameter tractable: for any fixed value of $c$ , it is possible to test whether a graph has cutwidth at most $c$ , and if so find an optimal vertex ordering for it, in linear time.^[2] More precisely, in terms of both $n$ and $c$ , the running time of this algorithm is ${\textstyle 2^{O(c^{2})}n}$ .^[14] An alternative parameterized algorithm, more suitable for graphs in which a small number of vertices have high degree (making the cutwidth large) instead solves the problem in time polynomial in $n$ when the graph has a vertex cover of bounded size, by transforming it into an integer programming problem with few variables and polynomial bounds on the variable values. It remains open whether the problem can be solved efficiently for graphs of bounded treewidth, which would subsume both of the parameterizations by cutwidth and vertex cover number.^[15]

Cutwidth has a polynomial-time approximation scheme for dense graphs,^[16] but for graphs that might not be dense the best approximation ratio known is ${\textstyle O{\bigl (}(\log n)^{3/2}{\bigr )}}$ .^[17] This comes from a method of Tom Leighton and Satish Rao for reducing approximate cutwidth to minimum bisection number, losing a factor of $\log _{2}n$ in the approximation ratio, by using recursive bisection to order the vertices.^[18] Combining this recursive bisection method with another method of Sanjeev Arora, Rao, and Umesh Vazirani for approximating the minimum bisection number,^[19] gives the stated approximation ratio.^[17] Under the small set expansion hypothesis, it is not possible to achieve a constant approximation ratio.^[17]

Applications

A channel routing problem, in which pairs of numbered pins must be connected along horizontal "channels" in a rectangular area

Solution using five channels

An early motivating application for cutwidth involved channel routing in VLSI design, in which components arranged along the top and bottom of a rectangular region of an integrated circuit should be connected by conductors that connect pairs pins attached to the components. If the components are free to be arranged into different left-to-right orders, but the pins of each component must remain contiguous, then this can be translated into a problem of choosing a linear arrangement of a graph with a vertex for each component and an edge for each pin-to-pin connection. The cutwidth of the graph controls the number of channels needed to route the circuit.^[5]

In protein engineering, an assumption that an associated graph has bounded cutwidth has been used to speed up the search for mRNA sequences that simultaneously code for a given protein sequence and fold into a given secondary structure.^[20]

A weighted variant of the problem applying to directed acyclic graphs, and only allowing linear orderings consistent with the orientation of the graph edges, has been applied to schedule a sequence of computational tasks in a way that minimizes the maximum amount of memory required in the schedule, both for the tasks themselves and to maintain the data used for task-to-task communication.^[21] In database theory, the NP-hardness of the cutwidth problem has been used to show that it is also NP-hard to schedule the transfer of blocks of data between a disk and main memory when performing a join, in order to avoid repeated transfers of the same block while fitting the computation within a limited amount of main memory.^[22]

In graph drawing, as well as being applied in the lower bound for crossing number,^[8] cutwidth has been applied in the study of a specific type of three-dimensional graph drawing, in which the edge are represented as disjoint polygonal chains with at most one bend, the vertices are placed on a line, and all vertices and bend points must have integer coordinates. For drawings of this type, the minimum volume of a bounding box of the drawing must be at least proportional to the cutwidth multiplied by the number of vertices. There always exists a drawing with this volume, with the vertices placed on an axis-parallel line.^[23]

Related Research Articles

In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph.

In graph theory, an undirected graph $H$ is called a minor of the graph $G$ if $H$ can be formed from $G$ by deleting edges, vertices and by contracting edges.

In graph theory, the metric dimension of a graph G is the minimum cardinality of a subset S of vertices such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP-hard problem; the decision version, determining whether the metric dimension is less than a given value, is NP-complete.

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing an acyclic subgraph of the given graph, often called a directed acyclic graph. A feedback arc set with the fewest possible edges is a minimum feedback arc set and its removal leaves a maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly $k$ are called $k$ -trees, and the graphs with treewidth at most $k$ are called partial $k$ -trees. Many other well-studied graph families also have bounded treewidth.

In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in a book, a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the spine, and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number.

In graph theory, a path decomposition of a graph $G$ is, informally, a representation of $G$ as a "thickened" path graph, and the pathwidth of $G$ is a number that measures how much the path was thickened to form $G$ . More formally, a path-decomposition is a sequence of subsets of vertices of $G$ 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 interval thickness, vertex separation number, or node searching number.

In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of vertices from an $n$ -vertex graph can partition the graph into disjoint subgraphs each of which has at most vertices.

In graph theory, the tree-depth of a connected undirected graph $is a numerical invariant of, the minimum height of a Trémaux tree for a supergraph of . This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages. Intuitively, where the treewidth of a graph measures how far it is from being a tree, this parameter measures how far a graph is from being a star.$

In graph theory, a caterpillar or caterpillar tree is a tree in which all the vertices are within distance 1 of a central path.

In graph theory, the graph bandwidth problem is to label the $n$ vertices $v i$ of a graph $G$ with distinct integers so that the quantity $is minimized . The problem may be visualized as placing the vertices of a graph at distinct integer points along the x -axis so that the length of the longest edge is minimized. Such placement is called linear graph arrangement, linear graph layout or linear graph placement .$

In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs $K 5$ or $K 3,3$ , every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.

In the study of graph algorithms, Courcelle's theorem is the statement that every graph property definable in the monadic second-order logic of graphs can be decided in linear time on graphs of bounded treewidth. The result was first proved by Bruno Courcelle in 1990 and independently rediscovered by Borie, Parker & Tovey (1992). It is considered the archetype of algorithmic meta-theorems.

In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge. If a 1-planar graph, one of the most natural generalizations of planar graphs, is drawn that way, the drawing is called a 1-plane graph or 1-planar embedding of the graph.

In graph theory, a branch of mathematics, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other. Indifference graphs are also the intersection graphs of sets of unit intervals, or of properly nested intervals. Based on these two types of interval representations, these graphs are also called unit interval graphs or proper interval graphs; they form a subclass of the interval graphs.

<span class="mw-page-title-main">Queue number</span> Invariant in graph theory

In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings.

In graph theory, a branch of mathematics, a chordal completion of a given undirected graph $G$ is a chordal graph, on the same vertex set, that has $G$ as a subgraph. A minimal chordal completion is a chordal completion such that any graph formed by removing an edge would no longer be a chordal completion. A minimum chordal completion is a chordal completion with as few edges as possible.

The twin-width of an undirected graph is a natural number associated with the graph, used to study the parameterized complexity of graph algorithms. Intuitively, it measures how similar the graph is to a cograph, a type of graph that can be reduced to a single vertex by repeatedly merging together twins, vertices that have the same neighbors. The twin-width is defined from a sequence of repeated mergers where the vertices are not required to be twins, but have nearly equal sets of neighbors.

In graph theory, the carving width of a graph is a number, defined from the graph, that describes the number of edges separating the clusters in a hierarchical clustering of the graph vertices.

References

1 2 3 Chung, Fan R. K. (1985). "On the cutwidth and the topological bandwidth of a tree" (PDF). SIAM Journal on Algebraic and Discrete Methods . 6 (2): 268–277. doi:10.1137/0606026. MR 0778007.
1 2 Thilikos, Dimitrios M.; Serna, Maria; Bodlaender, Hans L. (2005). "Cutwidth I: A linear time fixed parameter algorithm" (PDF). Journal of Algorithms . 56 (1): 1–24. doi:10.1016/j.jalgor.2004.12.001. MR 2146375.
↑ Korach, Ephraim; Solel, Nir (1993). "Tree-width, path-width, and cutwidth". Discrete Applied Mathematics . 43 (1): 97–101. doi: 10.1016/0166-218X(93)90171-J . MR 1218045.
1 2 Chung, F. R. K.; Seymour, P. D. (1989). "Graphs with small bandwidth and cutwidth" (PDF). Discrete Mathematics . 75 (1–3): 113–119. doi:10.1016/0012-365X(89)90083-6. MR 1001391.
1 2 Makedon, Fillia; Sudborough, Ivan Hal (1989). "On minimizing width in linear layouts". Discrete Applied Mathematics . 23 (3): 243–265. doi: 10.1016/0166-218X(89)90016-4 . MR 0996137.
↑ Díaz, Josep; Petit, Jordi; Serna, Maria (September 2002). "A survey of graph layout problems" (PDF). ACM Computing Surveys . 34 (3): 313–356. doi:10.1145/568522.568523.
↑ Seymour, Paul D.; Thomas, Robin (1994). "Call routing and the ratcatcher". Combinatorica. 14 (2): 217–241. doi:10.1007/BF01215352.
1 2 3 Djidjev, Hristo N.; Vrt'o, Imrich (2003). "Crossing numbers and cutwidths". Journal of Graph Algorithms and Applications . 7 (3): 245–251. doi: 10.7155/jgaa.00069 . MR 2112230.
↑ Stöhr, Elena (1988). "A trade-off between page number and page width of book embeddings of graphs". Information and Computation . 79 (2): 155–162. doi: 10.1016/0890-5401(88)90036-3 . MR 0968104.
↑ Yannakakis, Mihalis (1985). "A polynomial algorithm for the min-cut linear arrangement of trees". Journal of the ACM . 32 (4): 950–988. doi: 10.1145/4221.4228 . MR 0810346.
↑ Monien, B.; Sudborough, I. H. (1988). "Min cut is NP-complete for edge weighted trees". Theoretical Computer Science . 58 (1–3): 209–229. doi: 10.1016/0304-3975(88)90028-X . MR 0963264.
↑ Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M. (2012). "A note on exact algorithms for vertex ordering problems on graphs". Theory of Computing Systems. 50 (3): 420–432. doi:10.1007/s00224-011-9312-0. hdl: 1956/4556 . MR 2885638. S2CID 9967521.
↑ Ambainis, Andris; Balodis, Kaspars; Iraids, Jānis; Kokainis, Martins; Prūsis, Krišjānis; Vihrovs, Jevgēnijs (2019). "Quantum speedups for exponential-time dynamic programming algorithms". In Chan, Timothy M. (ed.). Proceedings of the Thirtieth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6–9, 2019. Society for Industrial and Applied Mathematics. pp. 1783–1793. arXiv: 1807.05209 . doi:10.1137/1.9781611975482.107. MR 3909576.
↑ Giannopoulou, Archontia C.; Pilipczuk, Jean-Florent, Michałand Raymond; Thilikos, Dimitrios M.; Wrochna, Marcin (2019). "Cutwidth: obstructions and algorithmic aspects" (PDF). Algorithmica. 81 (2): 557–588. doi:10.1007/s00453-018-0424-7. MR 3910081.{{cite journal}}: CS1 maint: multiple names: authors list (link)
↑ Fellows, Michael R.; Lokshtanov, Daniel; Misra, Neeldhara; Rosamond, Frances A.; Saurabh, Saket (2008). "Graph layout problems parameterized by vertex cover" (PDF). In Hong, Seok-Hee; Nagamochi, Hiroshi; Fukunaga, Takuro (eds.). Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15–17, 2008, Proceedings. Lecture Notes in Computer Science. Vol. 5369. Springer. pp. 294–305. doi:10.1007/978-3-540-92182-0_28.
↑ Arora, Sanjeev; Frieze, Alan; Kaplan, Haim (2002). "A new rounding procedure for the assignment problem with applications to dense graph arrangement problems". Mathematical Programming . 92 (1, Ser. A): 1–36. doi:10.1007/s101070100271. MR 1892295.
1 2 3 Wu, Yu; Austrin, Per; Pitassi, Toniann; Liu, David (2014). "Inapproximability of treewidth, one-shot pebbling, and related layout problems". Journal of Artificial Intelligence Research . 49: 569–600. doi: 10.1613/jair.4030 . MR 3195329.
↑ Leighton, Tom; Rao, Satish (1999). "Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms". Journal of the ACM . 46 (6): 787–832. doi: 10.1145/331524.331526 . MR 1753034.
↑ Arora, Sanjeev; Rao, Satish; Vazirani, Umesh (2009). "Expander flows, geometric embeddings and graph partitioning" (PDF). Journal of the ACM . 56 (2): Art. 5, 37. doi:10.1145/1502793.1502794. MR 2535878.
↑ Blin, Guillaume; Fertin, Guillaume; Hermelin, Danny; Vialette, Stéphane (2008). "Fixed-parameter algorithms for protein similarity search under mRNA structure constraints". Journal of Discrete Algorithms. 6 (4): 618–626. doi: 10.1016/j.jda.2008.03.004 . MR 2463425.
↑ Kayaaslan, Enver; Lambert, Thomas; Marchal, Loris; Uçar, Bora (2018). "Scheduling series-parallel task graphs to minimize peak memory". Theoretical Computer Science . 707: 1–23. doi: 10.1016/j.tcs.2017.09.037 . MR 3734396.
↑ Fotouhi, Farshad; Pramanik, Sakti (1991). "Problem of optimizing the number of block accesses in performing relational join is NP-hard". Information Processing Letters. 38 (5): 271–275. doi:10.1016/0020-0190(91)90070-X. MR 1114421.
↑ Morin, Pat; Wood, David R. (2004). "Three-dimensional 1-bend graph drawings". Journal of Graph Algorithms and Applications . 8 (3): 357–366. doi: 10.7155/jgaa.00095 . MR 2176967.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[chung-1] 1 2 3 Chung, Fan R. K. (1985). "On the cutwidth and the topological bandwidth of a tree" (PDF). SIAM Journal on Algebraic and Discrete Methods . 6 (2): 268–277. doi:10.1137/0606026. MR 0778007.

[tsb-2] 1 2 Thilikos, Dimitrios M.; Serna, Maria; Bodlaender, Hans L. (2005). "Cutwidth I: A linear time fixed parameter algorithm" (PDF). Journal of Algorithms . 56 (1): 1–24. doi:10.1016/j.jalgor.2004.12.001. MR 2146375.

[korsol-3] Korach, Ephraim; Solel, Nir (1993). "Tree-width, path-width, and cutwidth". Discrete Applied Mathematics . 43 (1): 97–101. doi: 10.1016/0166-218X(93)90171-J . MR 1218045.

[chusey-4] 1 2 Chung, F. R. K.; Seymour, P. D. (1989). "Graphs with small bandwidth and cutwidth" (PDF). Discrete Mathematics . 75 (1–3): 113–119. doi:10.1016/0012-365X(89)90083-6. MR 1001391.

[maksud-5] 1 2 Makedon, Fillia; Sudborough, Ivan Hal (1989). "On minimizing width in linear layouts". Discrete Applied Mathematics . 23 (3): 243–265. doi: 10.1016/0166-218X(89)90016-4 . MR 0996137.

[dps-6] Díaz, Josep; Petit, Jordi; Serna, Maria (September 2002). "A survey of graph layout problems" (PDF). ACM Computing Surveys . 34 (3): 313–356. doi:10.1145/568522.568523.

[seytho-7] Seymour, Paul D.; Thomas, Robin (1994). "Call routing and the ratcatcher". Combinatorica. 14 (2): 217–241. doi:10.1007/BF01215352.

[djivrt-8] 1 2 3 Djidjev, Hristo N.; Vrt'o, Imrich (2003). "Crossing numbers and cutwidths". Journal of Graph Algorithms and Applications . 7 (3): 245–251. doi: 10.7155/jgaa.00069 . MR 2112230.

[stohr-9] Stöhr, Elena (1988). "A trade-off between page number and page width of book embeddings of graphs". Information and Computation . 79 (2): 155–162. doi: 10.1016/0890-5401(88)90036-3 . MR 0968104.

[yannakakis-10] Yannakakis, Mihalis (1985). "A polynomial algorithm for the min-cut linear arrangement of trees". Journal of the ACM . 32 (4): 950–988. doi: 10.1145/4221.4228 . MR 0810346.

[monsud-11] Monien, B.; Sudborough, I. H. (1988). "Min cut is NP-complete for edge weighted trees". Theoretical Computer Science . 58 (1–3): 209–229. doi: 10.1016/0304-3975(88)90028-X . MR 0963264.

[bfkkt-12] Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M. (2012). "A note on exact algorithms for vertex ordering problems on graphs". Theory of Computing Systems. 50 (3): 420–432. doi:10.1007/s00224-011-9312-0. hdl: 1956/4556 . MR 2885638. S2CID 9967521.

[abikpv-13] Ambainis, Andris; Balodis, Kaspars; Iraids, Jānis; Kokainis, Martins; Prūsis, Krišjānis; Vihrovs, Jevgēnijs (2019). "Quantum speedups for exponential-time dynamic programming algorithms". In Chan, Timothy M. (ed.). Proceedings of the Thirtieth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6–9, 2019. Society for Industrial and Applied Mathematics. pp. 1783–1793. arXiv: 1807.05209 . doi:10.1137/1.9781611975482.107. MR 3909576.

[gprtw-14] Giannopoulou, Archontia C.; Pilipczuk, Jean-Florent, Michałand Raymond; Thilikos, Dimitrios M.; Wrochna, Marcin (2019). "Cutwidth: obstructions and algorithmic aspects" (PDF). Algorithmica. 81 (2): 557–588. doi:10.1007/s00453-018-0424-7. MR 3910081.{{cite journal}}: CS1 maint: multiple names: authors list (link)

[flmrs-15] Fellows, Michael R.; Lokshtanov, Daniel; Misra, Neeldhara; Rosamond, Frances A.; Saurabh, Saket (2008). "Graph layout problems parameterized by vertex cover" (PDF). In Hong, Seok-Hee; Nagamochi, Hiroshi; Fukunaga, Takuro (eds.). Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15–17, 2008, Proceedings. Lecture Notes in Computer Science. Vol. 5369. Springer. pp. 294–305. doi:10.1007/978-3-540-92182-0_28.

[afk-16] Arora, Sanjeev; Frieze, Alan; Kaplan, Haim (2002). "A new rounding procedure for the assignment problem with applications to dense graph arrangement problems". Mathematical Programming . 92 (1, Ser. A): 1–36. doi:10.1007/s101070100271. MR 1892295.

[wapl-17] 1 2 3 Wu, Yu; Austrin, Per; Pitassi, Toniann; Liu, David (2014). "Inapproximability of treewidth, one-shot pebbling, and related layout problems". Journal of Artificial Intelligence Research . 49: 569–600. doi: 10.1613/jair.4030 . MR 3195329.

[leirao-18] Leighton, Tom; Rao, Satish (1999). "Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms". Journal of the ACM . 46 (6): 787–832. doi: 10.1145/331524.331526 . MR 1753034.

[arv-19] Arora, Sanjeev; Rao, Satish; Vazirani, Umesh (2009). "Expander flows, geometric embeddings and graph partitioning" (PDF). Journal of the ACM . 56 (2): Art. 5, 37. doi:10.1145/1502793.1502794. MR 2535878.

[bfhv-20] Blin, Guillaume; Fertin, Guillaume; Hermelin, Danny; Vialette, Stéphane (2008). "Fixed-parameter algorithms for protein similarity search under mRNA structure constraints". Journal of Discrete Algorithms. 6 (4): 618–626. doi: 10.1016/j.jda.2008.03.004 . MR 2463425.

[klmu-21] Kayaaslan, Enver; Lambert, Thomas; Marchal, Loris; Uçar, Bora (2018). "Scheduling series-parallel task graphs to minimize peak memory". Theoretical Computer Science . 707: 1–23. doi: 10.1016/j.tcs.2017.09.037 . MR 3734396.

[fotpra-22] Fotouhi, Farshad; Pramanik, Sakti (1991). "Problem of optimizing the number of block accesses in performing relational join is NP-hard". Information Processing Letters. 38 (5): 271–275. doi:10.1016/0020-0190(91)90070-X. MR 1114421.

[morwoo-23] Morin, Pat; Wood, David R. (2004). "Three-dimensional 1-bend graph drawings". Journal of Graph Algorithms and Applications . 8 (3): 357–366. doi: 10.7155/jgaa.00095 . MR 2176967.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]