A. Abboud, F. Grandoni, and V. Williams, Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter, SODA'15, pp.1681-1697
DOI : 10.1137/1.9781611973730.112
URL : http://theory.stanford.edu/%7Evirgi/betw.pdf

A. Abboud and V. Williams, Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems, 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp.434-443
DOI : 10.1109/FOCS.2014.53

A. Abboud, V. Williams, and J. Wang, Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp.377-391
DOI : 10.1137/1.9781611974331.ch28

L. Babel, Tree-like P4-connected graphs, Discrete Mathematics, vol.191, issue.1-3, pp.13-23, 1998.
DOI : 10.1016/S0012-365X(98)00088-0
URL : https://doi.org/10.1016/s0012-365x(98)00088-0

L. Babel, Recognition and isomorphism of tree-like P4-connected graphs, Discrete Applied Mathematics, vol.99, issue.1-3, pp.295-315, 2000.
DOI : 10.1016/S0166-218X(99)00140-7

L. Babel and S. Olariu, On the structure of graphs with few P4s, Discrete Applied Mathematics, vol.84, issue.1-3, pp.1-31, 1998.
DOI : 10.1016/S0166-218X(97)90120-7

L. Babel and S. Olariu, On the p-connectedness of graphs ??? a survey, Discrete Applied Mathematics, vol.95, issue.1-3, pp.11-33, 1999.
DOI : 10.1016/S0166-218X(99)00062-1

H. Bandelt and H. Mulder, Distance-hereditary graphs, Journal of Combinatorial Theory, Series B, vol.41, issue.2
DOI : 10.1016/0095-8956(86)90043-2
URL : https://doi.org/10.1016/0095-8956(86)90043-2

M. Bentert, T. Fluschnik, A. Nichterlein, and R. Niedermeier, Parameterized Aspects of Triangle Enumeration, FCT'17, pp.96-110
DOI : 10.1109/ICDE.2012.35

C. Berge, TWO THEOREMS IN GRAPH THEORY, Proceedings of the National Academy of Sciences, vol.43, issue.9, pp.842-844, 1957.
DOI : 10.1073/pnas.43.9.842
URL : http://doi.org/10.1073/pnas.43.9.842

H. Bodlaender, Treewidth: Characterizations, Applications, and Computations, WG'06, pp.1-14
DOI : 10.1007/11917496_1
URL : http://www.cs.uu.nl/research/techreps/repo/CS-2006/2006-041.pdf

J. A. Bondy and U. S. Murty, Graph theory, Grad. Texts in Math, vol.244, 2008.
DOI : 10.1007/978-1-84628-970-5

M. Borassi, D. Coudert, P. Crescenzi, and A. Marino, On Computing the Hyperbolicity of Real-World Graphs, ESA'15, pp.215-226
DOI : 10.1080/15326349.2013.838510
URL : https://hal.archives-ouvertes.fr/hal-01199860

M. Borassi, P. Crescenzi, and M. Habib, Into the Square: On the Complexity of Some Quadratic-time Solvable Problems, Electronic Notes in Theoretical Computer Science, vol.322, pp.51-67, 2016.
DOI : 10.1016/j.entcs.2016.03.005
URL : https://hal.archives-ouvertes.fr/hal-01390131

P. Charbit, F. De-montgolfier, and M. Raffinot, Linear Time Split Decomposition Revisited, SIAM Journal on Discrete Mathematics, vol.26, issue.2, pp.499-514, 2012.
DOI : 10.1137/10080052X
URL : https://hal.archives-ouvertes.fr/hal-00921774

D. Corneil, M. Habib, J. Lanlignel, B. Reed, and U. Rotics, Polynomial Time Recognition of Clique- Width ? 3 Graphs, pp.126-134
URL : https://hal.archives-ouvertes.fr/hal-01274081

D. Corneil, Y. Perl, and L. Stewart, A Linear Recognition Algorithm for Cographs, SIAM Journal on Computing, vol.14, issue.4, pp.926-934, 1985.
DOI : 10.1137/0214065

D. Corneil and U. Rotics, On the Relationship Between Clique-Width and Treewidth, SIAM Journal on Computing, vol.34, issue.4, pp.825-847, 2005.
DOI : 10.1137/S0097539701385351

D. Coudert and G. Ducoffe, Recognition of $C_4$-Free and 1/2-Hyperbolic Graphs, SIAM Journal on Discrete Mathematics, vol.28, issue.3, pp.1601-1617, 2014.
DOI : 10.1137/140954787
URL : https://hal.archives-ouvertes.fr/hal-01070768

D. Coudert, G. Ducoffe, and A. Popa, Fully polynomial FPT algorithms for some classes of bounded cliquewidth graphs, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01676187

B. Courcelle, The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Information and computation, pp.12-75, 1990.
URL : https://hal.archives-ouvertes.fr/hal-00353765

B. Courcelle, On the model-checking of monadic second-order formulas with edge set quantifications, Discrete Applied Mathematics, vol.160, issue.6, pp.866-887, 2012.
DOI : 10.1016/j.dam.2010.12.017
URL : https://hal.archives-ouvertes.fr/hal-00481735

B. Courcelle, J. Engelfriet, and G. Rozenberg, Handle-rewriting hypergraph grammars, Journal of Computer and System Sciences, vol.46, issue.2, pp.218-270, 1993.
DOI : 10.1016/0022-0000(93)90004-G
URL : https://doi.org/10.1016/0022-0000(93)90004-g

B. Courcelle, P. Heggernes, D. Meister, C. Papadopoulos, U. Rotics et al., A characterisation of clique-width through nested partitions, Theory of Computing Systems, pp.70-81125, 2000.
DOI : 10.1016/j.dam.2015.02.016
URL : https://hal.archives-ouvertes.fr/hal-01022109

B. Courcelle and S. Olariu, Upper bounds to the clique width of graphs Decomposition of directed graphs, Discrete Applied Mathematics SIAM Journal on Algebraic Discrete Methods, vol.101, issue.32, pp.77-114214, 1982.

F. Dragan, On greedy matching ordering and greedy matchable graphs, WG'97, pp.184-198
DOI : 10.1007/BFb0024498

F. Dragan and F. Nicolai, LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem, Discrete Applied Mathematics, vol.98, issue.3, pp.191-207, 2000.
DOI : 10.1016/S0166-218X(99)00157-2

R. Duan and S. Pettie, Linear-Time Approximation for Maximum Weight Matching, Journal of the ACM, vol.61, issue.1, 2014.
DOI : 10.6028/jres.069B.009
URL : http://web.eecs.umich.edu/~pettie/papers/ApproxMWM-JACM.pdf

G. Ducoffe, Metric properties of large graphs, 2016.
URL : https://hal.archives-ouvertes.fr/tel-01485328

J. Edmonds, Paths, trees, and flowers, Journal canadien de math??matiques, vol.17, issue.0, pp.449-467, 1965.
DOI : 10.4153/CJM-1965-045-4

W. Espelage, F. Gurski, and E. Wanke, How to Solve NP-hard Graph Problems on Clique-Width Bounded Graphs in Polynomial Time, WG'11, pp.117-128
DOI : 10.1007/3-540-45477-2_12

J. Evald and S. Dahlgaard, Tight Hardness Results for Distance and Centrality Problems in Constant Degree Graphs, 2016.

M. Fellows, F. A. Rosamond, U. Rotics, and S. Szeider, Clique-Width is NP-Complete, SIAM Journal on Discrete Mathematics, vol.23, issue.2, pp.909-939, 2009.
DOI : 10.1137/070687256

T. Fluschnik, C. Komusiewicz, G. Mertzios, A. Nichterlein, R. Niedermeier et al., When Can Graph Hyperbolicity Be Computed in Linear Time?, WADS'17, pp.397-408
DOI : 10.1137/1.9781611973730.111

F. Fomin, D. Lokshtanov, M. Pilipczuk, S. Saurabh, and M. Wrochna, Fully polynomial-time parameterized computations for graphs and matrices of low treewidth, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.1419-1432
DOI : 10.1137/1.9781611974782.92

J. Fouquet, V. Giakoumakis, and J. Vanherpe, BIPARTITE GRAPHS TOTALLY DECOMPOSABLE BY CANONICAL DECOMPOSITION, International Journal of Foundations of Computer Science, vol.60, issue.04, pp.513-533, 1999.
DOI : 10.1016/S0020-0190(98)00173-2
URL : https://hal.archives-ouvertes.fr/hal-00467645

J. Fouquet, I. Parfenoff, and H. Thuillier, An O(n) time algorithm for maximum matching in P4-tidy graphs, Information Processing Letters, vol.62, issue.6, pp.281-287, 1997.
DOI : 10.1016/S0020-0190(97)00081-1

H. Fournier, A. Ismail, and A. Vigneron, Computing the Gromov hyperbolicity of a discrete metric space, Information Processing Letters, vol.115, issue.6-8, pp.576-579, 2015.
DOI : 10.1016/j.ipl.2015.02.002

L. Freeman, A Set of Measures of Centrality Based on Betweenness, Sociometry, vol.40, issue.1, pp.35-41, 1977.
DOI : 10.2307/3033543

H. Gabow and R. Tarjan, A linear-time algorithm for a special case of disjoint set union, STOC'83, pp.246-251

J. Gajarsk-`-gajarsk-`-y, M. Lampis, and S. Ordyniak, Parameterized Algorithms for Modular-Width, IPEC'13, pp.163-176
DOI : 10.1007/978-3-319-03898-8_15

A. Gajentaan and M. H. Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, vol.5, issue.3, pp.165-185, 1995.
DOI : 10.1016/0925-7721(95)00022-2

T. Gallai, Transitiv orientierbare Graphen, Acta Mathematica Academiae Scientiarum Hungaricae, vol.51, issue.1-2, pp.25-66, 1967.
DOI : 10.4153/CJM-1964-055-5

C. Gavoille and C. Paul, Distance labeling scheme and split decomposition, Discrete Mathematics, vol.273, issue.1-3, pp.115-130, 2003.
DOI : 10.1016/S0012-365X(03)00232-2
URL : https://hal.archives-ouvertes.fr/lirmm-00090364

V. Giakoumakis, F. Roussel, and H. Thuillier, On P4-tidy graphs, Discrete Mathematics and Theoretical Computer Science, vol.1, 1997.
URL : https://hal.archives-ouvertes.fr/hal-00955688

A. C. Giannopoulou, G. B. Mertzios, and R. Niedermeier, Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs, Theoretical Computer Science, vol.689, 2017.
DOI : 10.1016/j.tcs.2017.05.017

E. Gioan and C. Paul, Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs, Discrete Applied Mathematics, vol.160, issue.6, pp.708-733, 2012.
DOI : 10.1016/j.dam.2011.05.007
URL : https://hal.archives-ouvertes.fr/lirmm-00783420

M. Golumbic and U. Rotics, ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES, International Journal of Foundations of Computer Science, vol.11, issue.03, pp.423-443, 2000.
DOI : 10.1002/(SICI)1097-0118(199902)30:2<121::AID-JGT6>3.0.CO;2-1

M. Gromov, Hyperbolic Groups, Essays in group theory, pp.75-263, 1987.
DOI : 10.1007/978-1-4613-9586-7_3

F. Gurski and E. Wanke, The tree-width of cliquewidth bounded graphs without Kn,n, WG'00, pp.196-205

M. Habib and C. Paul, A survey of the algorithmic aspects of modular decomposition, Computer Science Review, vol.4, issue.1, pp.41-59, 2010.
DOI : 10.1016/j.cosrev.2010.01.001

T. Husfeldt, Computing graph distances parameterized by treewidth and diameter, IPEC'16, pp.1-1611

R. Impagliazzo, R. Paturi, and F. Zane, Which problems have strongly exponential complexity?, FOCS'98, pp.653-662
DOI : 10.1109/sfcs.1998.743516
URL : http://dimacs.rutgers.edu/~dieter/Seminar/Papers/ipz-strongexp.ps

B. Jamison and S. Olariu, P-Components and the Homogeneous Decomposition of Graphs, SIAM Journal on Discrete Mathematics, vol.8, issue.3, pp.448-463, 1995.
DOI : 10.1137/S0895480191196812

C. Jordan, Sur les assemblages de lignes., Journal f??r die reine und angewandte Mathematik (Crelles Journal), vol.1869, issue.70, p.81, 1869.
DOI : 10.1515/crll.1869.70.185

R. Karp and M. Sipser, Maximum matching in sparse random graphs, 22nd Annual Symposium on Foundations of Computer Science (sfcs 1981), pp.364-375
DOI : 10.1109/SFCS.1981.21

D. Kratsch and J. Spinrad, ), SIAM Journal on Computing, vol.36, issue.2, pp.310-325, 2006.
DOI : 10.1137/S0097539704441435

M. Lampis, Algorithmic Meta-theorems for Restrictions of Treewidth, Algorithmica, vol.4, issue.3, pp.19-37, 2012.
DOI : 10.1287/moor.8.4.538

J. Lanlignel, Autour de la décomposition en coupes, 2001.

J. Makowsky and U. Rotics, 'S, International Journal of Foundations of Computer Science, vol.6, issue.03, pp.329-348, 1999.
DOI : 10.1016/0166-218X(94)90026-4

G. Mertzios, A. Nichterlein, and R. Niedermeier, The power of data reduction for matching, MFCS'17

S. Micali and V. Vazirani, An O( ? V E) algorithm for finding maximum matching in general graphs, FOCS'80, pp.17-27

M. Novick, Fast parallel algorithms for the modular decomposition, 1989.

S. Olariu, Weak bipolarizable graphs, Discrete Mathematics, vol.74, issue.1-2, pp.159-171, 1989.
DOI : 10.1016/0012-365X(89)90208-2
URL : https://doi.org/10.1016/0012-365x(89)90208-2

S. Oum and P. Seymour, Approximating clique-width and branch-width, Journal of Combinatorial Theory, Series B, vol.96, issue.4, pp.514-528, 2006.
DOI : 10.1016/j.jctb.2005.10.006
URL : https://doi.org/10.1016/j.jctb.2005.10.006

R. Puzis, Y. Elovici, P. Zilberman, S. Dolev, and U. Brandes, Topology manipulations for speeding betweenness centrality computation, Journal of Complex Networks, vol.3, issue.1, pp.84-112, 2014.
DOI : 10.1093/comnet/cnu015

M. Rao, Clique-width of graphs defined by one-vertex extensions, Discrete Mathematics, vol.308, issue.24, pp.6157-6165, 2008.
DOI : 10.1016/j.disc.2007.11.039
URL : https://hal.archives-ouvertes.fr/lirmm-00808032

M. Rao, Solving some NP-complete problems using split decomposition, Discrete Applied Mathematics, vol.156, issue.14, pp.2768-2780, 2008.
DOI : 10.1016/j.dam.2007.11.013
URL : https://hal.archives-ouvertes.fr/lirmm-00324549

N. Robertson and P. Seymour, Graph minors. II. Algorithmic aspects of tree-width, Journal of Algorithms, vol.7, issue.3, pp.309-322, 1986.
DOI : 10.1016/0196-6774(86)90023-4
URL : https://doi.org/10.1006/jctb.1996.0059

L. Roditty and V. Williams, Fast approximation algorithms for the diameter and radius of sparse graphs, Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, STOC '13, pp.515-524
DOI : 10.1145/2488608.2488673

M. S. Gómez, Quelques propriétés topologiques des graphes et applicationsàapplicationsà internet et aux réseaux, 2011.

D. Sumner, Graphs indecomposable with respect to the X-join, Discrete Mathematics, vol.6, issue.3, pp.281-298, 1973.
DOI : 10.1016/0012-365X(73)90100-3

M. Tedder, D. Corneil, M. Habib, and C. Paul, Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations, ICALP'08, pp.634-645
DOI : 10.1007/978-3-540-70575-8_52
URL : http://www.cs.utoronto.ca/~mtedder/TedderModular.pdf

V. and V. Williams, Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (Invited talk), IPEC'15, pp.16-28

V. , V. Williams, and R. Williams, Subcubic Equivalences between Path, Matrix and Triangle Problems, 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp.645-654
DOI : 10.1109/FOCS.2010.67

M. Yu and C. Yang, An O(n) time algorithm for maximum matching on cographs, Information Processing Letters, vol.47, issue.2, pp.89-93, 1993.
DOI : 10.1016/0020-0190(93)90230-7