Nicolas Grelier

About

I am a PhD student at ETH Zürich, in the Theory of Combinatorial Algorithm Group. My supervisors are Dr. Michael Hoffmann and Prof. Emo Welzl.

I did my master in Brest at IMT Atlantique, where I had the opportunity to work on several research projects under the supervision of Prof. Vincent Gripon. During an academic exchange at Hong Kong University, I had the pleasure to work with Prof. Zhiyi Huang. I completed my end-of-studies internship at Radboud University Nijmegen under the supervision of Prof. Ross J. Kang.

Contact

Institute of Theoretical Computer Science Department of Computer Science
ETH Zürich, CAB G19.2
8092 Zürich
Switzerland

Phone: +41 44 632 42 86
E-mail: firstname.lastname{at}inf.ethz.ch

Publications and Manuscripts

  • Nearest-Neighbor Decompositions of Drawings
    Jonas Cleve, Kristin Knorr, Maarten Löffler, Wolfgang Mulzer and Daniel Perz
    To be presented at SWAT 2022

  • Well-Separation and Hyperplane Transversals in High Dimensions
    with Helena Bergold, Daniel Bertschinger, Wolfgang Mulzer and Patrick Schnider
    To be presented at SWAT 2022

  • Hardness and Approximation of Minimum Convex Partition
    To be presented at SoCG 2022

  • Computing a maximum clique in geometric superclasses of disk graphs
    In Journal of Combinatorial Optimization (2022) (A preliminary version appeared in the Proceedings of COCOON 2020).

  • Maximum Clique in Disk-Like Intersection Graphs
    with Édouard Bonnet and Tillmann Miltzow
    To appear in Proceedings of FSTTCS 2020.

  • On the VC-dimension of convex sets and half-spaces
    with Saeed Gh. Ilchi, Tillmann Miltzow and Shakhar Smorodinsky.
    In Discrete Mathematics & Theoretical Computer Science, 23:2 (2021), #2.

  • Approximate strong edge-colouring of unit disk graphs
    with Rémi de Joannis de Verclos, Ross J. Kang and François Pirot.
    In Proceedings of WAOA, 154-169, 2019.

  • Graph-Projected Signal Processing
    with Carlos R. K. Lassance, Elsa Dupraz and Vincent Gripon.
    In Proceedings of IEEE GlobalSIP, 763-767, 2018.

  • Neighborhood-preserving translations on graphs
    with Bastien Pasdeloup, Jean-Charles Vialatte and Vincent Gripon.
    In Proceedings of IEEE GlobalSIP, 410--414, October 2016.
  • Supervised Theses

    Jela Kovacevic, Universal Geometric Representations of Graphs, Master thesis, to be completed
    Luca Pinter, Covering Points with Lines, Bachelor thesis, February 2022
    Ning Gao, The maximum geometric subgraph problem, Master thesis, September 2021, with Meghana M. Reddy
    Valentin Stoppiello, Perfect Coarsening and Slack for Triangulation Flips Graphs in Higher Dimensions, Master thesis, September 2021, with Patrick Schnider and Emo Welzl
    Valentin Stoppiello, The structure of triangulation flip graphs in dimension 3 and beyond, Semester thesis, February 2021, with Emo Welzl
    Ari Jordan, Routing in Convex Partitions with Few Edges, Bachelor thesis, February 2021, with Michael Hoffmann
    Philip Jordan, Discrete and Computational Geometry on the Sphere, Bachelor thesis, October 2020, with Emo Welzl

    Talks and Poster Sessions

    Approximation of Minimum Convex Partition, EuroCG 2022, Perugia, Italy, March 2022

    Nearest-Neighbor Decompositions of Drawings, EuroCG 2021, online, April 2021

    Maximum Clique in Disk-Like Intersection Graphs, FSTTCS 2020, online, December 2020

    Computing a maximum clique in geometric superclasses of disk graphs, COCOON 2020, online, August 2020

    Minimum Convex Partition of Degenerate Point Sets is NP-Hard, EuroCG 2020, online, March 2020

    Approximate strong edge-colouring of unit disk graphs, WAOA 2019, Germany, September 2019

    Approximate strong edge-colouring of unit disk graphs, EuroCG 2019, Utrecht, The Netherlands, March 2019

    Graph-Projected Signal Processing GSP18, EPFL, Switzerland, June 2018

    Neighborhood-preserving translations on graphs GlobalSIP 2016, Washington D.C., USA, December 2016