CNRS researcher
Member of the AlGCo Group (Algorithms, Graphs & Combinatorics),
from LIRMM (CNRS & Université de Montpellier).

École de théorie des graphs à Sète en juin prochain ! SGT 2018

Research Interests

  • Topological Graphs, in particular through the lens of Schnyder Woods.
  • Intersection Graphs, such as String, Segment, $t$-Interval graphs.
  • Graph Coloring, in particular with the Entropy Compression Method.
  • Algorithms: FPT, Approx, Hardness results.


  • On triangles in $K_r$-minor free graphs (with B. Albar) Journal of Graph Theory doi:10.1002/jgt.22203, to appear. ArXiv Sagemath code here.
  • Planar Graphs as L-intersection or L-contact graphs (with L.~Isenmann and C.~Pennarun). Proc. of SODA 2018, 2018. ArXiv
  • The k-strong Induced Arboricity of a Graph (with M. Axenovich, J. Rollin, and T. Ueckerdt). Eur. J. of Combin. 67, 1-20, 2018. ArXiv
  • Dushnik-Miller dimension of contact systems of $d$-dimensional boxes (with M.C. Francis). EUROCOMB 2017, 2017.
  • Dushnik-Miller dimension of TD-Delaunay complexes (with L. Isenmann). EuroCG 2017, 2017.
  • Encoding toroidal triangulations (with V. Despré, B. Lévêque). Disc. & Comp. Geom. 57 (3), 507-544, 2017. ArXiv
  • A Polynomial-time Algorithm for Outerplanar Diameter Improvement (with N. Cohen, E.J. Kim, C. Paul, I. Sau, D.M. Thilikos, and M. Weller). J. of Comput. and Syst. Sci., 89, 315-327, 2017. ArXiv
  • Structure of Schnyder labelings on orientable surfaces (with K. Knauer, B. Lévêque). ArXiv
  • Orienting triangulations (with B. Albar and K. Knauer). Journal of Graph Theory 83(4), 392-405, 2016. ArXiv
  • Entropy compression method applied to graph colorings (with M. Montassier and A. Pinlou).ArXiv
  • Coloring Non-Crossing Strings (with L.Esperet and A. Labourel) Elec. J. of Combin. 23(4): #4, 18 pp, 2016. pdf
  • Detecting minors in matroids through triangles (with B. Albar and J.L. Ramírez Alfonsín). European Journal of Combinatorics 53: 50-58, 2016. ArXiv
  • Maximum Independent Set in EPG Graphs (with S. Bessy, M. Bougeret, and C. Paul). Proceedings of WAOA '15, LNCS 9499, 158-169. ArXiv
  • Two floor building needing eight colors (with S. Bessy and J.-S. Sereni) Journal of Graph Algorithms and Applications, Vol. 19, no. 1, pp. 1-9, 2015. JGAA
  • Toroidal Maps: Schnyder Woods, Orthogonal Surfaces and Straight-Line Representations (with B. Lévêque) Disc. & Comp. Geom., 51(1): 67-131, 2014. ArXiv
  • Parameterized Domination in Circle Graphs (with N. Bousquet, G. Mertzios, C. Paul, I. Sau and S. Thomassé) Theo. Of Comp. Syst., 54(1): 45-72, 2014. ArXiv
  • The Maximum Clique Problem in Multiple Interval Graphs (with M.C. Francis and P. Ochem) Algorithmica 71 (4), 812-836, 2015. ArXiv
  • On Exact Algorithms for the Permutation CSP (with E.J. Kim) Theo. Comp. Sci., 511, 109-116, 2013. ArXiv
  • Locally identifying coloring in bounded expansion classes of graphs (with A. Parreau and A. Pinlou) Disc. Appl. Math. 161 (18), 2946-2951, 2013. ArXiv
  • Partitioning the arcs of a digraph into a star forests of the underlying graph with prescribed orientation properties (with J. Bang-Jensen and A. Yeo), Theo. Comp. Sci., 475, 13-20, 2013.
  • Triangle contact representations and duality (with B. Lévêque and A. Pinlou) Discrete & Computational Geometry 48(1): 239-254, 2012. see also the Proceedings of Graph Drawing '10.
  • Spanning galaxies in digraphs (with F. Havet, A. Pinlou and S. Thomassé) Discrete Applied Mathematics 160(6): 744-754, 2012. pdf
  • The Domination Number of Grids (with A. Pinlou, M. Rao and S. Thomassé) SIAM J. Discrete Math., 25 (3), 1443-1453, 2011. ArXiv
  • Every planar graph is the intersection graph of segments in the plane. (with J. Chalopin) STOC 2009. pdf
  • Diamond-free Circle Graphs are Helly Circle. (with J. Daligault and M. Rao) Discrete Math. 310 (4), 845-849, 2010. pdf
  • On Vertex Partitions and some Minor-Monotone Parameters. J. of Graph Theory 66 (1), 49--56, 2010. pdf
  • On star and caterpillar arboricity. (with P. Ochem) Discrete Math. 309 (11), 3694--3702, 2009. pdf
  • A Planar linear hypergraph whose edges cannot be represented as straight line segments. Eur. J. Combin. 30, 280-282, 2009. pdf
  • Covering planar graphs with forests, one having bounded maximum degree. J. Combin. Theory Ser. B 99 (2), 314-322, 2009. pdf
  • On the L(p,1)-labelling of graphs. Discrete Math. 308 (8), 1405-1414, 2008. pdf
  • Finding well-balanced pairs of edge-disjoint trees in edge-weighted graphs. (with J. Bang-Jensen and I.L. Gørtz) Discrete Optimization 4 (3-4), 334-348, 2007. pdf
  • Caterpillar arboricity of planar graphs. Discrete Math. 307 (16), 2112-2121, 2007. pdf
  • Planar graphs are in 1-STRING. (with J. Chalopin and P. Ochem) Disc. Comput. Geom 43 (3), 626-647, 2010. pdf
  • On graph classes defined by overlap and intersection models. (with J. Chalopin and P. Ochem) CS '06.
  • Edge Partition of Planar Graphs into Two Outerplanar Graphs. STOC '05. pdf
  • Acyclic choosability of graphs with small maximum degree. (with M. Montassier) WG '05. pdf
  • On Oriented Labelling Parameters. (with A. Raspaud and M.A. Shalu) Formal Models, Languages and Applications, Series in Machine Perception and artificial Intelligence Vol. 66, World Scientific, Singapore. Chap. 3, p. 34-45, 2006. pdf

Research project

  • I am a member of the ANR GATO Project.

Internship Opportunities