G. =. Then-cw-1, v n be an ordering of V (G) such that cw ? (G) ? k. Let also S be the set of endpoints of the edges in F . Clearly |S| ? 2w We define a set of indices I ? {1, . . . , n} such that {v i | i ? I} = S. A pair (i, j) ? I 2 is consecutive if there is no h ? I such that i < h < j. Among all consecutive pairs in I 2 let (i, j) be one maximizing the value c = j ? i ? 1. This implies that c ? (n ? 2w)/(w + 1) ? . Consider now the set X = {v i+1 , . . . , v j?1 } and observe that |X| = c ? . Notice that if ? = v i+1, j?1 , then cw ? (G[X]) ? k. Moreover there are at most ? G ({v 1 , . . . , v i }) + ? G ({v j , . . . , v n }) ? 2k edges with one vertex in X and the other not in X. Therefore, ? G (X) ? 2k and X is a (2k, k)-cutwidth-edge-protrusion of G

L. Hans and . Bodlaender, A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput, vol.25, issue.6, pp.1305-1317, 1996.

L. Hans, T. Bodlaender, and . Kloks, Efficient and constructive algorithms for the pathwidth and treewidth of graphs, J. Algorithms, vol.21, issue.2, pp.358-402, 1996.

H. Booth, R. Govindan, M. A. Langston, and S. Ramachandramurthi, Cutwidth approximation in linear time, [1992] Proceedings of the Second Great Lakes Symposium on VLSI, pp.70-73, 1992.
DOI : 10.1109/GLSV.1992.218363

D. Chatzidimitriou, J. Raymond, I. Sau, and D. M. Thilikos, An O(log OP T ) -approximation for covering/packing minor models of ? r, Proceedings of WAOA 2015, pp.122-132, 2015.

J. Díaz, J. Petit, and M. J. Serna, A survey of graph layout problems, ACM Computing Surveys, vol.34, issue.3, pp.313-356, 2002.
DOI : 10.1145/568522.568523

V. Fedor, D. Fomin, N. Lokshtanov, S. Misra, and . Saurabh, Planar F-deletion: Approximation, kernelization and optimal FPT algorithms, Proceedings of FOCS 2012, pp.470-479, 2012.

R. Michael, D. S. Garey, and . Johnson, Computers and intractability, 1979.

C. Archontia, . Giannopoulou, J. Pilipczuk, D. M. Raymond, M. Thilikos et al., Linear kernels for edge deletion problems to immersion-closed graph classes, 2016.

R. Govindan and S. Ramachandramurthi, A weak immersion relation on graphs and its applications, Discrete Mathematics, vol.230, issue.1-3, pp.189-206, 2001.
DOI : 10.1016/S0012-365X(00)00080-7

P. Heggernes, D. Lokshtanov, R. Mihai, and C. Papadopoulos, Cutwidth of Split Graphs and Threshold Graphs, SIAM Journal on Discrete Mathematics, vol.25, issue.3, pp.1418-1437, 2011.
DOI : 10.1137/080741197

P. Heggernes, D. Pim-van-'t-hof, J. Lokshtanov, and . Nederlof, Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time, SIAM Journal on Discrete Mathematics, vol.26, issue.3, pp.1008-1021, 2012.
DOI : 10.1137/110830514

E. Korach and N. Solel, Tree-width, path-width, and cutwidth, Discrete Applied Mathematics, vol.43, issue.1, pp.97-101, 1993.
DOI : 10.1016/0166-218X(93)90171-J

J. Lagergren, Upper Bounds on the Size of Obstructions and Intertwines, Journal of Combinatorial Theory, Series B, vol.73, issue.1, pp.7-40, 1998.
DOI : 10.1006/jctb.1997.1788

F. Thomson, L. , and S. Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, J. ACM, vol.46, issue.6, pp.787-832, 1999.

N. Robertson and P. D. Seymour, Graph minors XXIII. Nash-Williams' immersion conjecture, Journal of Combinatorial Theory, Series B, vol.100, issue.2, pp.181-205, 2010.
DOI : 10.1016/j.jctb.2009.07.003

D. Paul, R. Seymour, and . Thomas, Call routing and the ratcatcher, Combinatorica, vol.14, issue.2, pp.217-241, 1994.

A. Takahashi, S. Ueno, and Y. Kajitani, Minimal acyclic forbidden minors for the family of graphs with bounded path-width, Graph theory and applications (Hakone, pp.293-304, 1990.
DOI : 10.1016/0012-365X(94)90092-2

D. M. Thilikos, M. J. Serna, and H. L. Bodlaender, Cutwidth I: A linear time fixed parameter algorithm, Journal of Algorithms, vol.56, issue.1, pp.1-24, 2005.
DOI : 10.1016/j.jalgor.2004.12.001

D. M. Thilikos, M. J. Serna, and H. L. Bodlaender, Cutwidth II: Algorithms for partial w-trees of bounded degree, Journal of Algorithms, vol.56, issue.1, pp.25-49, 2005.
DOI : 10.1016/j.jalgor.2004.12.003

R. Thomas, A menger-like property of tree-width: The finite case, Journal of Combinatorial Theory, Series B, vol.48, issue.1, pp.67-76, 1990.
DOI : 10.1016/0095-8956(90)90130-R

P. Wollan, The structure of graphs not admitting a fixed immersion, Journal of Combinatorial Theory, Series B, vol.110, pp.47-66, 2015.
DOI : 10.1016/j.jctb.2014.07.003

M. Yannakakis, A polynomial algorithm for the min-cut linear arrangement of trees, Journal of the ACM, vol.32, issue.4, pp.950-988, 1985.
DOI : 10.1145/4221.4228