Publications

Reconfiguration of unit squares and disks: PSPACE-hardness in simple settings
with Mikkel Abrahamsen, Kevin Buchin, Maike Buchin, Maarten Löffler, Lena Schlipf, André Schulz, Jack Stade
in Proceedings of the 41st International Symposium on Computational Geometry (SoCG 2025)
doi: https://doi.org/10.4230/LIPIcs.SoCG.2025.1
arXiv: 2412.21017
Counterexample to Winkler's conjecture on Venn diagrams
with Sofia Brenner, Torsten Mütze, Christian Rieck, Francesco Verciani
arXiv: 2503.18554
A solution to Ringel's problem [pdf] [video]
with James Davies, Chaya Keller, Shakhar Smorodinsky, and Bartosz Walczak
Journal of the European Mathematical Society (JEMS), 2024
in Proceedings of 38th Symposium on Computational Geometry (SoCG 2022)
arXiv: 2112.05042
doi: 10.4171/jems/1557
media attention: [video], [Gil Kalai's blog], [NRC article][Haaretz article]
Geometric Embeddability of Complexes is ∃R-complete [pdf]
with Mikkel Abrahamsen and Tillmann Miltzow
in Proceedings of 39th Symposium on Computational Geometry (SoCG 2023)
Journal version in Journal of the ACM
arXiv: 2108.02585
doi: 10.1145/3707201
Flipping Non-Crossing Spanning Trees
with Håvard Bjerkevik, Torsten Ueckerdt, and Birgit Vogtenhuber
Symposium on Discrete Algorithms (SODA 2025)
arXiv: 2410.23809
doi: 10.1137/1.9781611978322.77
Facet-Hamiltonicity
with Hugo Akitaya, Jean Cardinal, Stefan Felsner, Robert Lauff
Symposium on Discrete Algorithms (SODA 2025)
arXiv: 2411.02172
doi: 10.1137/1.9781611978322.171
Complexity of Recognizing Geometric Hypergraphs
with Daniel Bertschinger, Nicolas El Maalouly, Tillmann Miltzow, Simon Weber
Journal version in Innovations in Graph Theory, Volume 2 (2025), pp. 157-190
Preprint of Extended Abstract appears in the proceedings of 39th European Workshop on Computational Geometry (EuroCG 2023)
in Proceedings of 31st International Symposium on Graph Drawing and Network Visualization
arXiv: 2302.13597
Minimum Plane Bichromatic Spanning Trees
with Hugo Akitaya, Ahmad Biniaz, Erik Demaine, Frederick Stock and Csaba Toth
35th International Symposium on Algorithms and Computation (ISAAC 2024), LIPIcs, Volume 322
arXiv: 2409.11614
doi: 10.4230/LIPIcs.ISAAC.2024.4
Emergence of power-law distributions in protein-protein interaction networks through study bias
with David B. Blumenthal , Marta Lucchetta, Sándor P. Fekete, Markus List and Martin H Schaefer
in Computational and Systems Biology
doi: 10.7554/eLife.99951
The Tripartite-Circle Crossing Number of Graphs With Two Small Partition Classes
with Charles Camacho, Silvia Fernández-Merchant, Marija Jelić Milutinović, Rachel Kirsch, Elizabeth Matson, Jennifer White
in Computing in Geometry and Topology, 2024
doi: 10.57717/cgt.v3i1.63
Strongly-Connected Minimal-Cost Radio-Networks Among Fixed Terminals Using Mobile Relays and Avoiding No-Transmission Zones [pdf]
with Francesco Bernardini, Daniel Biediger, Ileana Pineda, Aaron T. Becker
International Conference on Automation Science and Engineering (Case 2024)
doi: 10.1109/CASE59546.2024.10711430
arXiv: 2504.03747
On the Connectivity of the Flip Graph of Plane Spanning Paths [pdf]
with Peter Kramer and Christian Rieck
International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2024)
doi: 10.1007/978-3-031-75409-8_23
Augmenting Plane Straight-Line Graphs to Meet Parity Constraints. [pdf]
with Aleksander Christiansen, Irene Parada, and Eva Rotenberg
International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2024)
doi: 10.1007/978-3-031-75409-8_9
arXiv: 2502.10066
Online Sorting and Translational Packing of Convex Polygons [pdf]
with Anders Aamand, Mikkel Abrahamsen and Lorenzo Beretta
in Proceedings of Symposium on Discrete Algorithms (SODA 2023).
arXiv: 22112.03791.
The Complexity of the Hausdorff Distance [pdf]
with Paul Jungeblut and Tillmann Miltzow
Journal version in Discrete and Computational Geometry (DCG), 2023
in Proceedings of 38th Symposium on Computational Geometry (SoCG 2022)
arXiv: 2112.04343
Adjacency Graphs of Polyhedral Surfaces [pdf]
with Elena Arseneva, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber and Alexander Wolff.
Journal version in Discrete and Computational Geometry (DCG), 2023
in Proceedings of 37th Symposium on Computational Geometry (SoCG 2021)
Preprint of Extended Abstract in 36th European Workshop on Computational Geometry (EuroCG 2020)
arXiv: 2103.09803
Completeness for the Complexity Class ∀∃ℝ and Area-Universality [pdf]
with Michael G. Dobbins, Tillmann Miltzow, and Pawel Rzazewski
Journal version in Discrete and Computational Geometry (DCG), 2022
in Proceedings of WG 2018, LNCS 11159
arXiv:1712.05142
The tripartite-circle crossing number of graphs with two small partition classes [pdf]
with Charles Camacho, Silvia Fernandez-Merchant, Marija Jelic, Rachel Kirsch, Elizabeth Bailey Matson, and Jennifer White
arXiv: 2108.01032
Packing Squares into a Disk with Optimal Worst-Case Density [pdf]
with Sándor P. Fekete, Vijay Gurunathan, Kushagra Juneja, Phillip Keldenich, Christian Scheffer
Journal version in Special Issue of Journal of Computational Geometry (JoCG), devoted to selected papers from SoCG 2021
in Proceedings of 37th Symposium on Computational Geometry (SoCG 2021)
Preprint of Extended Abstract in36th European Workshop on Computational Geometry (EuroCG 2020) , video talk [video]
arXiv: 2103.07258.
Training Neural Networks is ER-complete [pdf]
with Mikkel Abrahamsen and Tillmann Miltzow
in Proceedings of 35th Conference on Neural Information Processing Systems (NeurIPS 2021)
arXiv: 2102.09798
Scheduling with Machine Conflicts [pdf]
with Moritz Buchem and Daniel Schmidt genannt Waldschmidt
in Proceedings of International Workshop on Approximation and Online Algorithms (WAOA 2022)
arXiv: 2102.08231
Bounding the tripartite-circle crossing number of complete tripartite graphs [pdf]
with Charles Camacho, Silvia Fernandez-Merchant, Marija Jelic, Rachel Kirsch, Elizabeth Bailey Matson, and Jennifer White
Journal version in Journal of Graph Theory (JGT), 2022
in Proceedings of EuroComb 2019 [extended abstract]
Our poster won the Best Poster Award at GD 2018 [poster][abstract]
arXiv: 1910.06963.
Folding Polyiamonds into Octahedra [pdf]
with Eva Stehr (previously Bolle)
Journal version in Computational Geometry (CGTA), 2022
in Proceedings of 33rd Canadian Conference on Computational Geometry (CCCG 2021) [pdf]
Preprint of Extended Abstract in37th European Workshop on Computational Geometry (EuroCG 2021) [booklet]
Minimum Scan Cover and Variants -- Theory and Experiments [pdf]
with Kevin Buchin, Sándor Fekete, Alexander Hill, Irina Kostitsyna, Dominik Krupke, Roel Lambers, and Martijn Struijs
Journal version in ACM Journal of Experimental Algorithmics (JEA), 2022
in Proceedings of 19th International Symposium on Experimental Algorithms (SEA 2021)
arXiv: 2103.14599
Minimum Scan Cover with Angular Transition Costs [pdf]
with Sándor Fekete and Dominik Krupke
Journal version in Siam Journal on Discrete Mathematics (SIDMA), 2021
in Proceedings of 36th Symposium on Computational Geometry (SoCG 2020)
arXiv: 2003.08816
On Area-Universal Quadrangulations [pdf]
with William Evans, Stefan Felsner, and Stephen Kobourov
in Journal of Graph Algorithms and Applications (JGAA), 2021
Upward Point Set Embeddings of Paths and Trees
with Elena Arseneva, Pilar Cano, Tamara Mchedlidze, Saeed Mehrabi, Irene Parada, Pavel Valtr
in Proceedings of 15th International Conference and Workshops on Algorithms and Computing (WALCOM 2021)
arXiv: 2012.10525.
Competitive Location Problems: Balanced Facility Location and the One-Round Manhattan Voronoi Game [pdf]
with Thomas Byrne, Sándor Fekete, Jörg Kalcsics
in Proceedings of 15th International Conference and Workshops on Algorithms and Computing (WALCOM 2021)
arXiv: 2011.13275
Folding Polyominoes with Holes into a Cube [pdf]
with Oswin Aichholzer, Hugo Akitaya, Kenneth C. Cheung, Erik Demaine, Martin Demaine, Sándor Fekete, Irina Kostitsyna, Maarten Löffler, Zuzana Masárová
Journal Version in Computational Geometry (CGTA), 2020
in Proceedings of CCCG 2019[pdf]
arXiv: 1910.09917
Rainbow Cycles in Flip Graphs [pdf] [slides]
with Stefan Felsner, Torsten Mütze, and Leon Sering
Journal version in Siam Journal on Discrete Mathematics (SIDMA), 2020
in Proceedings of 34th Symposium on Computationnal Geometry (SoCG 2018)
arXiv: 1712.07421.
Targeted Drug Delivery: Algorithmic Methods for Collecting a Swarm of Particles with Uniform, External Forces. [pdf]
with Aaron T. Becker, Sándor P. Fekete, Li Huang, Phillip Keldenich, Dominik Krupke, Christian Rieck, Arne Schmidt
in Proceedings of IEEE International Conference on Robotics and Automation (ICRA)
Preprint in Proceedings of 36th European Workshop on Computational Geometry (EuroCG 2020)
Convexity-Increasing Morphs [pdf]
with Boris Klemz, Anna Lubiw, Lena Schlipf, Frank Staals, Darren Strash
Journal version in Computational Geometry - Theory and Applications (CGTA), 2019
Conference version WG 2018, LNCS 11159
arXiv: 1802.06579
On the Edge-Vertex Ratio of Maximal Thrackles [pdf]
with Oswin Aichholzer, Boris Klemz, Felix Schröder, Birgit Vogtenhuber
in Proceedings of GD 2019, LNCS 11904.
arXiv: 1908.08857.
Drawing Planar Graphs with Prescribed Face Areas [pdf] [slides]
Journal Version in Journal of Computational Geometry (JoCG) 2018 [pdf]
in Proceedings of WG 2016, LNCS 9941 [pdf]
On the Area-Universality of Triangulations [pdf]
in Proceedings of GD 2018, LNCS 11282 [pdf]
arXiv: 1808.10864
Planar Graphs and Face Areas -- Area-Universality [pdf]
PhD thesis, TU Berlin, 2018
doi: 10.14279/depositonce-7674
Upper and Lower Bounds on Long Dual-Paths in Line Arrangements [pdf] [slides]
with Udo Hoffmann and Tillmann Miltzow
in MFCS 2015 , LNCS 9235
arXiv: 1506.03728
Unit Contact Representations of Grid Subgraphs with Regular Polytopes in 2D and 3D [pdf] [slides]
with Benjamin Rahman
in Proceedings of GD 14, LNCS 8871