Esther Galby

Assistant and PhD Student

T: +41 26 300 8320

Address: Bd de Pérolles 90, 1700 Fribourg

Office: C 309

Email

 


 

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


 

Teaching activities

 


 

Publications

  • 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, accepted to MFCS, to appear in LIPICs (available on arxiv)
  • Blocking dominating sets for H-free graphs via edge contractions, E. Galby, P. T. Lima, B. Ries, submitted (available on arxiv)
  • CPG graphs: some structural and hardness results, E. Galby, A. Munaro, B. Ries, submitted (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, submitted (available on arxiv)

 


 

Grants

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