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

  • Bachelor Courses:
    • Decision Support I (in french), Fall Semester 2018
  • Master Courses:
    • Graph Theory and Applications (in english), Fall Semester 2018
    • Advanced Topics in Decision Support (in english), Spring Semester 2019

 


 

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. Ries, Information 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, to appear in Discrete Applied Mathematics (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)

  • On the Parametrized Complexity of k-Edge ColouringE. Galby, P. T. Lima, D. Paulusma, B. Ries, submitted (available on  arxiv)
  • Reducing the domination number of 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)