@article{3063490,
    title = "Cutwidth: Obstructions and Algorithmic Aspects",
    author = "Giannopoulou, A.C. and Pilipczuk, M. and Raymond, J.-F. and Thilikos, D.M. and Wrochna, M.",
    journal = "Algorithmica (New York)",
    year = "2019",
    volume = "81",
    number = "2",
    pages = "557-588",
    publisher = "Springer New York LLC",
    doi = "10.1007/s00453-018-0424-7",
    keywords = "Algorithms, Algorithmic aspects;  AS graph;  Combinatorics;  Cutwidths;  Fixed-parameter algorithms;  Fixed-parameter tractability;  Immersions;  Obstructions, Computer science",
    abstract = "Cutwidth is one of the classic layout parameters for graphs. It measures how well one can order the vertices of a graph in a linear manner, so that the maximum number of edges between any prefix and its complement suffix is minimized. As graphs of cutwidth at most k are closed under taking immersions, the results of Robertson and Seymour imply that there is a finite list of minimal immersion obstructions for admitting a cut layout of width at most k. We prove that every minimal immersion obstruction for cutwidth at most k has size at most 2O(k3logk). As an interesting algorithmic byproduct, we design a new fixed-parameter algorithm for computing the cutwidth of a graph that runs in time 2O(k2logk)·n, where k is the optimum width and n is the number of vertices. While being slower by a log k-factor in the exponent than the fastest known algorithm, given by Thilikos et al. (J Algorithms 56(1):1–24, 2005; J Algorithms 56(1):25–49, 2005), our algorithm has the advantage of being simpler and self-contained; arguably, it explains better the combinatorics of optimum-width layouts. © 2018, The Author(s)."
}