CNRS researcher

Member of the AlGCo Group (Algorithms, Graphs & Combinatorics),

from LIRMM (CNRS & Université de Montpellier).

# 2nd JCRAALMA (march-april 2021) : program

# 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.

# Articles

**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**3-Colorable Planar Graphs Have an Intersection Segment Representation Using 3 Slopes**WG 2019.**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*, 2020.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).*EuroCG 2017*, 2017. 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. 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

# Research project

- I am a member of the ANR GATO Project.