Esther Galby

Assistant and PhD Student

T: +41 26 300 8320

Address: Bd de Pérolles 90, 1700 Fribourg

Office: C 309




What my PhD thesis is about

Intersection (resp. contact) graphs of various type of geometrical objects have been considered in the literature. The object we are here interested in are paths on a grid; we say that a graph is an intersection (resp. contact) graph of paths on a grid, or EPG (resp. CPG) for short, if there exists a collection of paths (resp. interiorly disjoint paths) on a grid in one-to-one correspondence with its vertex set such that two vertices are adjacent if and only if the corresponding paths share a grid-edge (resp. a grid-point).

It was shown early on that every graph is in fact an EPG graph. Thus, additional restrictions were introduced, namely that of limiting the number of bends (i.e. 90-degree turns at a grid-point) that a path may have: for some $k \geq 0$, the class of $B_k$-EPG graphs consists of those EPG graphs admitting a representation in which every path has at most $k$ bends (one can similarly define the class of $B_k$-CPG graphs). If $B_k$-EPG graphs have been extensively studied since their introduction, very little is known about ($B_k$-)CPG graphs. Our intent is to study those graphs from a structural point of view so as to better understand their behaviour.


PhD advisor: Prof. Bernard Ries


Curriculum Vitae

A detailed CV can be found here.


Teaching activities




  • On Matrix Powering in Low Dimensions, E. Galby, J. Ouaknine, J. Worrell, 32nd Symposium on Theoretical Aspects of Computer Science - STACS (2015), LIPIcs 329--340, doi
  • On contact graphs of paths in  gridZ. Deniz, E. Galby, A. Munaro, B. Ries, Lecture Notes in Computer Science 11282, Graph Drawing 2018, 317--330 (2019), doi
  • Classifying k-edge colouring for H-free graphs, E. Galby, P. T. Lima, D. Paulusma, B. RiesInformation Processing Letters 146 39--43 (2019), doi 
  • Proper circular arc graphs as intersection graphs of paths in a grid, E. Galby, M.P. Mazzoleni, B. Ries, Discrete Applied Mathematics  262 195-202 (2019), doi
  • Reducing the domination number of graphs via edge contractions, E. Galby, P.T. Lima, B. Ries, Leibniz International Proceedings in Informatics 138 41:1 - 41:13 (2019), 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019),  doi
  • Blocking dominating sets for H-free graphs via edge contractions, E. Galby, P. T. Lima, B. Ries, to appear in Leibniz International Proceedings in Informatics (accepted to ISAAC 2019) (available on arxiv)
  • Semitotal Domination: New hardness results and a polynomial-time algorithm for graphs of bounded mim-width, E. Galby, A. Munaro, B. Ries, Theoretical Computer Science 814 28-48, doi
  • CPG graphs: some structural and hardness results, N. Champseix, E. Galby, A. Munaro, B. Ries, submittedto appear in Discrete Applied Mathematics (available on arxiv)
  • Approximating Independent Set and Dominating Set on VPG graphs, E. Galby, A. Munaro, submitted
  • Characterising Circular-arc Contact B_0-VPG Graphs, F. Bonomo-Braberman, E. Galby, C.L. Gonzalez, submitted (available on arxiv)
  • Reducing the domination number of graphs via edge contractions and vertex deletions, E. Galby, P.T. Lima, B. Ries, to appear in Discrete Mathematics

  • Blocking total dominating sets via edge contractions, E. Galby, F. Mann, B. Ries, submitted 




2019 : Mobility Grant from the Leading House for the Latin American Region