Cutwidth

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

[1] Both the vertex ordering that produces the cutwidth, and the problem of computing this ordering and the cutwidth, have been called minimum cut linear arrangement.

[5] The cutwidth is greater than or equal to the minimum bisection number of any graph.

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.

[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.

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.

[9] The cutwidth can be found, and a linear layout of optimal width constructed, in time

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

, and if so find an optimal vertex ordering for it, in linear time.

[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

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.

[17] This comes from a method of Tom Leighton and Satish Rao for reducing approximate cutwidth to minimum bisection number, losing a factor of

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] 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.

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.

There always exists a drawing with this volume, with the vertices placed on an axis-parallel line.