with: Jesper Nederlof • Karol Węgrzycki
Journal of the ACM 72(6), 42:1--42:48 (2025)
Journals
A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
A Quadtree, a Steiner Spanner, and Approximate Nearest Neighbours in Hyperbolic Space
with: Geert van Wordragen
Journal of Computational Geometry 16(2): 145--174 (2025)
Computing Smallest Convex Intersecting Polygons
with: Antonios Antoniadis • Mark de Berg • Antonis Skarlatos
Journal of Computational Geometry 16(1): 167--202 (2025)
Euclidean TSP in Narrow Strips
with: Henk Alkema • Mark de Berg • Remco van der Hofstad
Discret. Comput. Geom. 71(4): 1456--1506 (2024)
An ETH-Tight Exact Algorithm for Euclidean TSP
with: Mark de Berg • Hans L. Bodlaender • Sudeshna Kolay
SIAM J. Comput. 52(3): 740--760 (2023)
Clique-Based Separators for Geometric Intersection Graphs
with: Mark de Berg • Morteza Monemizadeh • Leonidas Theocharous
Algorithmica 85(6): 1652--1678 (2023)
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves
with: Karl Bringmann • Marvin Künnemann • Dániel Marx • André Nusser
Journal of Computational Geometry 14(2): 83--107 (2023)
Online search for a hyperplane in high-dimensional Euclidean space
with: Antonios Antoniadis • Ruben Hoeksma • Kevin Schewior
Information Processing Letters 177: 106262 (2022)
A quasi-polynomial algorithm for well-spaced hyperbolic TSP
Journal of Computational Geometry 12(2): 25--54 (2021)
Nearly ETH-tight algorithms for Planar Steiner Tree with Terminals
on Few Faces
with: Jesper Nederlof • Erik Jan van Leeuwen
ACM Transactions on Algorithms 16(3), p 28:1–28:30 (2020)
A Framework for Exponential-Time-Hypothesis-Tight Algorithms and
Lower Bounds in Geometric Intersection Graphs
with: Mark de Berg • Hans L. Bodlaender • Dániel Marx • Tom C. van der Zanden
SIAM J. Comput. 49(6): 1291--1331 (2020)
The Homogeneous Broadcast Problem in Narrow and Wide Strips I:
Algorithms
with: Mark de Berg • Hans L. Bodlaender
Algorithmica 81(7), p 2934–2962 (2019)
The Homogeneous Broadcast Problem in Narrow and Wide Strips II:
Lower Bounds
with: Mark de Berg • Hans L. Bodlaender
Algorithmica 81(7), p 2963–2990 (2019)
The complexity of Dominating Set in geometric intersection
graphs
with: Mark de Berg • Gerhard J. Woeginger
Theoretical Computer Science 769, p 18–31 (2019)
On the number of touching pairs in a set of planar curves
with: Péter Györgyi • Bálint Hujter
Computational Geometry: Theory and Applications 67, p 29–37 (2018)
Conferences
Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
with: Dániel Marx
58th Annual ACM Symposium on Theory of Computing (STOC)
To appear (2026)
Charting the Diameter Computation Landscape on Intersection Graphs in the Plane
with: Timothy M. Chan • Hsien-Chih Chang • Jie Gao • Hung Le • Da Wei Zheng
53rd International Colloquium on Automata, Languages, and Programming (ICALP)
To appear (2026)
Touring a Sequence of Orthogonal Polygons
with: Katrin Casel • Linda Kleist • Jeroen S. K. Lamme • Eunjin Oh • Yanheng Wang
53rd International Colloquium on Automata, Languages, and Programming (ICALP)
To appear (2026)
Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree
with: Saeed Odak • Satyam Singh • Geert van Wordragen
42nd International Symposium on Computational Geometry (SoCG)
New Brunswick, NJ, US (2026), 64:1--64:17
Near-Optimal Dynamic Steiner Spanners for Constant-Curvature Spaces
with: Geert van Wordragen
42nd International Symposium on Computational Geometry (SoCG)
New Brunswick, NJ, US (2026), 65:1--65:17
Charting the Diameter Computation Landscape of Intersection Graphs in 3D and Above
with: Timothy M. Chan • Hsien-Chih Chang • Jie Gao • Hung Le • Da Wei Zheng
42nd International Symposium on Computational Geometry (SoCG)
New Brunswick, NJ, US (2026), 29:1--29:15
Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity
with: Sujoy Bhore • Lazar Milenković • Csaba D. Tóth • Karol Węgrzycki • Sampson Wong
42nd International Symposium on Computational Geometry (SoCG)
New Brunswick, NJ, US (2026), 15:1--15:18
Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
with: Timothy M. Chan • Hsien-Chih Chang • Jie Gao • Hung Le • Da Wei Zheng
66th IEEE Annual Symposium on Foundations of Computer Science (FOCS)
Sydney, AU (2025), p 2728--2765
Structure and Independence in Hyperbolic Uniform Disk Graphs
with: Thomas Bläsius • Jean-Pierre von der Heydt • Marcus Wilhelm • Geert van Wordragen
41st International Symposium on Computational Geometry (SoCG)
Kanazawa, JP (2025)
Realizing Metric Spaces with Convex Obstacles
with: Leonidas Theocharous
36th International Symposium on Algorithms and Computation (ISAAC)
Tainan, TW (2025)
A Quadtree, a Steiner Spanner, and Approximate Nearest Neighbours in Hyperbolic Space
with: Geert van Wordragen
40th International Symposium on Computational Geometry (SoCG)
Athens, GR (2024)
Separator Theorem and Algorithms for Planar Hyperbolic Graphs
with: Jana Masaríková • Erik Jan van Leeuwen • Bartosz Walczak • Karol Wegrzycki
40th International Symposium on Computational Geometry (SoCG)
Athens, GR (2024)
Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification
with: Esther Galby • Dániel Marx • Roohani Sharma
51st International Colloquium on Automata, Languages, and Programming (ICALP)
Tallinn, EE (2024)
Computing Smallest Convex Intersecting Polygons
with: Antonios Antoniadis • Mark de Berg • Antonis Skarlatos
30th Annual European Symposium on Algorithms (ESA)
Berlin, DE (2022)
On the Approximability of the Traveling Salesman Problem with Line
Neighborhoods
with: Antonios Antoniadis • Bundit Laekhanukit • Daniel Vaz
18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT)
Tórshavn, FRO (2022)
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves
with: Karl Bringmann • Marvin Künnemann • Dániel Marx • André Nusser
38th International Symposium on Computational Geometry (SoCG)
Berlin, DE (2022)
Towards sub-quadratic diameter computation in geometric intersection graphs
with: Karl Bringmann • Marvin Künnemann • André Nusser • Zahra Parsaeian
38th International Symposium on Computational Geometry (SoCG)
Berlin, DE (2022)
Computing list homomorphisms in geometric intersection graphs
with: Karolina Okrasa • Paweł Rzążewski
Graph-Theoretic Concepts in Computer Science - 48th International Workshop, (WG)
Tübingen, DE (2022)
A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
with: Jesper Nederlof • Karol Węgrzycki
62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS).
2021-22 Denver, CO, USA
Clique-Based Separators for Geometric Intersection Graphs
with: Mark de Berg • Morteza Monemizadeh • Leonidas Theocharous
32nd International Symposium on Algorithms and Computation (ISAAC)
2021 Fukuoka, JP
A quasi-polynomial algorithm for well-spaced hyperbolic TSP
36th International Symposium on Computational Geometry (SoCG)
2020 Zürich, CH
Euclidean TSP in Narrow Strips
with: Henk Alkema • Mark de Berg
36th International Symposium on Computational Geometry (SoCG)
2020 Zürich, CH
Hyperbolic intersection graphs and (quasi)-polynomial time
31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
2020 Salt Lake City, UT, USA
On One-Round Discrete Voronoi Games
with: Mark de Berg • Mehran Mehr
30th International Symposium on Algorithms and Computation, (ISAAC)
2019 Shanghai, CN
How Does Object Fatness Impact the Complexity of Packing in d
Dimensions?
with: Dániel Marx • Tom van der Zanden
30th International Symposium on Algorithms and Computation, (ISAAC)
2019 Shanghai, CN
On Geometric Set Cover for Orthants
with: Karl Bringmann • Michał Pilipczuk • Erik Jan van Leeuwen
27th Annual European Symposium on Algorithms, (ESA)
2019 Munich/Garching, DE
Nearly ETH-tight algorithms for Planar Steiner Tree with Terminals
on Few Faces
with: Jesper Nederlof • Erik Jan van Leeuwen
30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
2019 San Diego, CA, US
An ETH-Tight Exact Algorithm for Euclidean TSP
with: Mark de Berg • Hans L. Bodlaender • Sudeshna Kolay
59th Annual IEEE Symposium on Foundations of Computer Science (FOCS)
2018 Paris, FR
A framework for ETH-tight algorithms and lower bounds in geometric
intersection graphs
with: Mark de Berg • Hans L. Bodlaender • Dániel Marx • Tom C. van der Zanden
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC)
2018 Los Angeles, CA, US
The Dominating Set Problem in Geometric Intersection Graphs
with: Mark de Berg • Gerhard J. Woeginger
International Symposium on Parameterized and Exact Computation (IPEC)
2017 Vienna, AT
The Homogeneous Broadcast Problem in Narrow and Wide Strips
with: Mark de Berg • Hans L. Bodlaender
Workshop on Algorithms and Data Structures (WADS)
2017 St. John's, CA
On the Exact Complexity of Hamiltonian Cycle and q-Colouring in
Disk Graphs
with: Tom C. van der Zanden
International Conference on Algorithms and Complexity (CIAC)
2017 Athens, GR
Connected Dominating Set on Unit Disk Graphs is W[1]-hard
with: Mark de Berg • Hans L. Bodlaender
European Workshop on Computational Geometry (EuroCG)
2016 Lugano, CH
Succinct tree coding for greedy navigation
with: Zoltán Király
9th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications
2015 Fukuoka, JP
Notes on dual-critical graphs
with: Zoltán Király
8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications
2013 Veszprém, HU
Book chapters
Lower Bounds for Dominating Set in Ball Graphs and for Weighted
Dominating Set in Unit-Ball Graphs
with: Mark de Berg
Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L.
Bodlaender on the Occasion of His 60th Birthday
In: Fomin F., Kratsch S., van Leeuwen E. (eds) Treewidth, Kernels,
and Algorithms. Lecture Notes in Computer Science, vol 12160.
Springer, Cham., p 31–48
Theses
ETH-tight algorithms for geometric network problems
advisors: Mark de Berg • Hans L. Bodlaender
TU Eindhoven, Department of Mathematics and Computer Science
2019
recipient.Preprints and Technical Reports
Precision in Geometric Algorithms (Dagstuhl Seminar 25372)
with: Mikkel Abrahamsen • Linda Kleist • Till Miltzow
Dagstuhl Reports 15(9): 21--37 (2026)
Shortest Paths, Convexity, and Treewidth in Regular Hyperbolic Tilings
with: Tze-Yang Poon • Geert van Wordragen
2025
Dual-Critical Graphs: Notes on parity constrained orientations
EGRES Technical Report 2012-07
with: Zoltán Király
2012