L. Hans, T. Bodlaender, D. Kloks, and . Kratsch, Treewidth and pathwidth of permutation graphs, SIAM J. Discrete Math, vol.8, issue.4, pp.606-616, 1995.

L. Hans, R. H. Bodlaender, and . Möhring, The pathwidth and treewidth of cographs, SIAM J. Discrete Math, vol.6, issue.2, pp.181-188, 1993.

H. L. Bodlaender, J. R. Gilbert, H. Hafsteinsson, and T. Kloks, Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree, Journal of Algorithms, vol.18, issue.2, pp.238-255, 1995.
DOI : 10.1006/jagm.1995.1009
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.7198

D. Coudert and D. Mazauric, Network reconfiguration using cops-and-robber games, 2008.
URL : https://hal.archives-ouvertes.fr/inria-00315568

D. Coudert, S. Perennes, Q. Pham, and J. Sereni, Rerouting requests in wdm networks, AlgoTel'05, pp.17-20, 2005.
URL : https://hal.archives-ouvertes.fr/inria-00429173

D. Coudert and J. Sereni, Characterization of graphs and digraphs with small process numbers, Discrete Applied Mathematics, vol.159, issue.11, 2007.
DOI : 10.1016/j.dam.2011.03.010

N. Deo, S. Krishnamoorthy, and M. A. Langston, Exact and Approximate Solutions for the Gate Matrix Layout Problem, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.6, issue.1, pp.79-84, 1987.
DOI : 10.1109/TCAD.1987.1270248

F. Fomin and D. Thilikos, An annotated bibliography on guaranteed graph searching, Theoretical Computer Science, vol.399, issue.3, pp.236-245, 2008.
DOI : 10.1016/j.tcs.2008.02.040
URL : http://doi.org/10.1016/j.tcs.2008.02.040

N. Jose and A. K. Somani, Connection rerouting/network reconfiguration. Design of Reliable Communication Networks, pp.23-30, 2003.
DOI : 10.1109/drcn.2003.1275334

M. Kirousis and C. H. Papadimitriou, Searching and pebbling, Theoretical Computer Science, vol.47, issue.2, pp.205-218, 1986.
DOI : 10.1016/0304-3975(86)90146-5
URL : http://doi.org/10.1016/0304-3975(86)90146-5

K. Lu, G. Xiao, and I. Chlamtac, Analysis of blocking probability for distributed lightpath establishment in WDM optical networks, IEEE/ACM Trans. Netw, vol.13, issue.1, pp.187-197, 2005.

N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson, and C. H. Papadimitriou, The complexity of searching a graph, Journal of the ACM, vol.35, issue.1, pp.18-44, 1988.
DOI : 10.1145/42267.42268

N. Robertson and P. D. Seymour, Graph minors. I. Excluding a forest, Journal of Combinatorial Theory, Series B, vol.35, issue.1, pp.39-61, 1983.
DOI : 10.1016/0095-8956(83)90079-5
URL : http://doi.org/10.1006/jctb.1999.1919

P. Saengudomlert, E. Modiano, and R. Gallager, On-line routing and wavelength assignment for dynamic traffic in WDM ring and torus networks, IEEE/ACM Transactions on Networking, vol.14, issue.2, pp.330-340, 2006.
DOI : 10.1109/TNET.2006.872549

K. Skodinis, Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time, Journal of Algorithms, vol.47, issue.1, pp.40-59, 2003.
DOI : 10.1016/S0196-6774(02)00225-0

K. Suchan and I. Todinca, Pathwidth of Circular-Arc Graphs, Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pp.258-269, 2007.
DOI : 10.1007/978-3-540-74839-7_25
URL : https://hal.archives-ouvertes.fr/hal-00462302

. Unité-de-recherche-inria-sophia and . Antipolis, route des Lucioles -BP 93 -06902 Sophia Antipolis Cedex (France) Unité de recherche INRIA Futurs : Parc Club Orsay Université -ZAC des Vignes 4, 2004.

I. Unité-de-recherche and . Lorraine, Technopôle de Nancy-Brabois -Campus scientifique 615, rue du Jardin Botanique -BP 101 -54602 Villers-lès-Nancy Cedex (France) Unité de recherche INRIA Rennes : IRISA, Campus universitaire de Beaulieu -35042 Rennes Cedex (France) Unité de recherche INRIA Rhône-Alpes : 655, avenue de l'Europe -38334 Montbonnot Saint-Ismier (France) Unité de recherche INRIA Rocquencourt, Domaine de Voluceau -Rocquencourt -BP 105 -78153 Le Chesnay Cedex

I. De-voluceau-rocquencourt, BP 105 -78153 Le Chesnay Cedex (France) http://www.inria.fr ISSN, pp.249-6399