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
A detailed CV can be found here.
- Bachelor Courses:
- Decision Support I (in french), Fall Semester 2019
- 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 grid, Z. 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, 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)
- 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, to appear in Theoretical Computer Science (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, submitted
2019 : Mobility Grant from the Leading House for the Latin American Region