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

Research Interests

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

Articles

  • Contact graphs of boxes with unidirectional contacts (with V. Limouzy, and P. Ochem) in preparation.
  • Partitioning into degenerate graphs in linear time (with T. Corsini, Q. Deschamps, C. Feghali, H. Langlois, and A. Talon) submitted ArXiv
  • On Comparable Box Dimension (with Z. Dvorák, A. Lahiri, J. Tan, and T. Ueckerdt) SoCG '22 LIPIcs 224 proceedings ArXiv
  • Complexity of some arc-partition problems for digraphs (with J.Bang-Jensen, S.Bessy, and L. Picasarri-Arrieta) Theoretical Computer Science in press, 2022. journal
  • Avoiding large squares in trees and planar graphs (with P. Ochem, and M. Rosenfeld) ArXiv
  • Not all planar graphs are in PURE-4-DIR Journal of Graph Algorithms and Applications 24(3): 293-301, 2020. here
  • Acyclic coloring of graphs and entropy compression method (with M. Montassier and A. Pinlou) Discrete Mathematics 343(4), 2020.ArXiv
  • Dushnik-Miller dimension of stair contact complexes (with Lucas Isenmann) EuroComb 2019.
  • 3-Colorable Planar Graphs Have an Intersection Segment Representation Using 3 Slopes WG 2019 pdf.
  • Homothetic triangle representations of planar graphs (with B. Lévêque and A. Pinlou) Journal of Graph Algorithms and Applications 23(4): 745-753, 2019. here
  • Every Collinear Set in a Planar Graph is Free (with V. Dujmovic, F. Frati, P. Morin and G. Rote) SODA 2019 and Discrete and Computational Geometry 65: 999-1027, 2021. ArXiv
  • Structure of Schnyder labelings on orientable surfaces (with K. Knauer, B. Lévêque). Journal of Computational Geometry, 10(1): 127-163, 2019. ArXiv
  • On triangles in $K_r$-minor free graphs (with B. Albar) Journal of Graph Theory 88(1): 154-173, 2018. ArXiv Sagemath code here
  • Planar Graphs as L-intersection or L-contact graphs (with L.~Isenmann and C.~Pennarun). Proc. of SODA 2018, 172-184, 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. ArXiv
  • Dushnik-Miller dimension of TD-Delaunay complexes (with L. Isenmann). European Journal of Combinatorics 88, 103-110, 2020. ArXiv
  • 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
  • Orienting triangulations (with B. Albar and K. Knauer). Journal of Graph Theory 83(4), 392-405, 2016. 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. On independent set in $B_1$-EPG graphs (with S. Chaplick) Discrete Applied Mathematics 278: 62-72, 2020. journal 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
  • The Maximum Clique Problem in Multiple Interval Graphs (with M.C. Francis and P. Ochem) Algorithmica 71 (4), 812-836, 2015. ArXiv
  • 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
  • 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