Department of Computer Science | Institute of Theoretical Computer Science | Theory of Combinatorial Algorithms

Michael Hoffmann

Department of Computer Science
ETH Zürich, OAT Z13.1
Andreasstrasse 5
CH-8092 Zürich

Papers

• "The Number of Edges in Maximal 2-Planar Graphs"
  with Meghana M. Reddy.
  Appeared in Proc. 39th International Symposium on Computational Geometry (SoCG '23), Leibniz Internat. Proc. Informatics (LIPIcs), Volume 258, Berlin, Germany, 2023, 39:1–39:15.
  
  
• "Drawings of Complete Multipartite Graphs up to Triangle Flips"
  with Oswin Aichholzer, Man Kwun Chiu, Hung Hoang, Jan Kynčl, Yannic Maus, Birgit Vogtenhuber, and Alexandra Weinberger.
  Appeared in Proc. 39th International Symposium on Computational Geometry (SoCG '23), Leibniz Internat. Proc. Informatics (LIPIcs), Volume 258, Berlin, Germany, 2023, 6:1–6:16.
  
  
• "Universal Geometric Graphs"
  with Fabrizio Frati and Csaba D. Tóth.
  Appeared in Combinatorics, Probability and Computing, Volume First View, 2023, 1–20.
  
  
• "Hamiltonian Cycles and Matchings in 1-planar Graphs"
  with Meghana M. Reddy and Emanuel Seemann.
  Appeared in Abstracts 39th European Workshop on Computational Geometry (EuroCG '23), Barcelona, Spain, 2023, 34:1–34:7.
  
  
• "The Number of Edges in Maximal 2-Planar Graphs"
  with Meghana M. Reddy.
  Appeared in Abstracts 39th European Workshop on Computational Geometry (EuroCG '23), Barcelona, Spain, 2023, 42:1–42:7.
  
  
• "Bounding and Computing Obstacle Numbers of Graphs"
  with Martin Balko, Steven Chaplick, Robert Ganian, Siddharth Gupta, Pavel Valtr, and Alexander Wolff.
  Appeared in Proc. 30th European Sympos. Algorithms (ESA '22), Leibniz Internat. Proc. Informatics (LIPIcs), Volume 244, Potsdam, Germany, 2022, 11:1–11:13.
  
  
• "On the Maximum Number of Crossings in Star-Simple Drawings of K_n with No Empty Lens"
  with Stefan Felsner, Kristin Knorr, Jan Kynčl, and Irene Parada.
  Appeared in Journal of Graph Algorithms and Applications, Volume 26(3), 2022, 381–399.
  
  
• "Drawing Shortest Paths in Geodetic Graphs"
  with Sabine Cornelsen, Maximilian Pfister, Henry Förster, Martin Gronemann, Stephen Kobourov, and Thomas Schneck.
  Appeared in Journal of Graph Algorithms and Applications, Volume 26(3), 2022, 353–361.
  
  
• "Long Plane Trees"
  with Sergio Cabello, Katharina Klost, Wolfgang Mulzer, and Josef Tkadlec.
  Appeared in Proc. 38th International Symposium on Computational Geometry (SoCG '22), Leibniz Internat. Proc. Informatics (LIPIcs), Volume 224, Berlin, Germany, 2022, 23:1–23:17.
  
  
• "Gioan's Theorem for complete bipartite graphs" (PDF)
  with Oswin Aichholzer, Man Kwun Chiu, Hung Hoang, Yannic Maus, Birgit Vogtenhuber, and Alexandra Weinberger.
  Appeared in Abstracts 38th European Workshop on Computational Geometry (EuroCG '22), Perugia, Italy, 2022, 31:1–31:6.
  
  
• "Long plane trees"
  with Sergio Cabello, Katharina Klost, Wolfgang Mulzer, and Josef Tkadlec.
  Appeared in Abstracts 37th European Workshop on Computational Geometry (EuroCG '21), St. Petersburg, Russia, 2021, 33:1–33:8.
  
  
• "Halving Balls by a Hyperplane in Deterministic Linear Time"
  with Vincent Kusters and Tillmann Miltzow.
  Appeared in Journal of Computational Geometry, Volume 11(1), 2020, 576–614.
  
  
• "Minimal Representations of Order Types by Geometric Graphs"
  with Oswin Aichholzer, Martin Balko, Jan Kynčl, Wolfgang Mulzer, Irene Parada, Alexander Pilz, Manfred Scheucher, Pavel Valtr, Birgit Vogtenhuber, and Emo Welzl.
  Appeared in Journal of Graph Algorithms and Applications, Volume 24(4), 2020, 551–572.
  
  
• "Drawing Shortest Paths in Geodetic Graphs"
  with Sabine Cornelsen, Maximilian Pfister, Henry Förster, Martin Gronemann, Stephen Kobourov, and Thomas Schneck.
  Appeared in Proc. 28th International Symposium on Graph Drawing & Network Visualization (GD '20), Lecture Notes in Computer Science, Volume 12590, Vancouver, Canada, 2020, 333–340.
  
  
• "On the Maximum Number of Crossings in Star-Simple Drawings of K_n with No Empty Lens"
  with Stefan Felsner, Kristin Knorr, and Irene Parada.
  Appeared in Proc. 28th International Symposium on Graph Drawing & Network Visualization (GD '20), Lecture Notes in Computer Science, Volume 12590, Vancouver, Canada, 2020, 382–389.
  
  
• "Simple Topological Drawings of k-Planar Graphs"
  with Chih Hung Liu, Meghana M. Reddy, and Csaba D. Tóth.
  Appeared in Proc. 28th International Symposium on Graph Drawing & Network Visualization (GD '20), Lecture Notes in Computer Science, Volume 12590, Vancouver, Canada, 2020, 390–402.
  
  
• "Plane Spanning Trees in Edge-Colored Simple Drawings of K_n"
  with Oswin Aichholzer, Johannes Obenaus, Rosna Paul, Daniel Perz, Nadja Seiferth, Birgit Vogtenhuber, and Alexandra Weinberger.
  Appeared in Proc. 28th International Symposium on Graph Drawing & Network Visualization (GD '20), Lecture Notes in Computer Science, Volume 12590, Vancouver, Canada, 2020, 482–489.
  
  
• "Universal Geometric Graphs"
  with Fabrizio Frati and Csaba D. Tóth.
  Appeared in 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '20), Lecture Notes in Computer Science, Volume 12301, Leeds, UK, 2020, 174–186.
  
  
• "Simple k-Planar Graphs are Simple (k + 1)-Quasiplanar"
  with Patrizio Angelini, Michael A. Bekos, Franz J. Brandenburg, Giordano Da Lozzo, Giuseppe Di Battista, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani, Ignaz Rutter, and Csaba D. Tóth.
  Appeared in J. Combin. Theory Ser. B, Volume 142, 2020, 1–35.
  
  
• "Monotone Arc Diagrams with few Biarcs"
  with Steven Chaplick and Henry Förster and Michael Kaufmann.
  Appeared in Abstracts 36th European Workshop on Computational Geometry (EuroCG '20), Würzburg, Germany, 2020, 46:1–46:7.
  
  
• "A Better Approximation for Longest Noncrossing Spanning Trees"
  with Sergio Cabello, Aruni Choudhary, Katharina Klost, Wolfgang Mulzer, Meghana M. Reddy, Felix Schröder, and Josef Tkadlec.
  Appeared in Abstracts 36th European Workshop on Computational Geometry (EuroCG '20), Würzburg, Germany, 2020, 77:1–77:8.
  
  
• "On the Maximum Number of Crossings in Star-simple Drawings of $K_n$ with No Empty Lens"
  with Stefan Felsner, Kristin Knorr, and Irene Parada.
  Appeared in Abstracts 36th European Workshop on Computational Geometry (EuroCG '20), Würzburg, Germany, 2020, 79:1–79:7.
  
  
• "The QuaSEFE Problem"
  with Patrizio Angelini, Henry Förster, Michael Kaufmann, Stephen Kobourov, Giuseppe Liotta, and Maurizio Patrignani.
  Appeared in Proc. 27th International Symposium on Graph Drawing & Network Visualization (GD '19), Lecture Notes in Computer Science, Volume 11904, Prague, Czech Republic, 2019, 268–275.
  
  
• "Minimal Representations of Order Types by Geometric Graphs"
  with Oswin Aichholzer, Martin Balko, Jan Kynčl, Wolfgang Mulzer, Irene Parada, Alexander Pilz, Manfred Scheucher, Pavel Valtr, Birgit Vogtenhuber, and Emo Welzl.
  Appeared in Proc. 27th International Symposium on Graph Drawing & Network Visualization (GD '19), Lecture Notes in Computer Science, Volume 11904, Prague, Czech Republic, 2019, 101–113.
  
  
• "Triconnected Planar Graphs of Maximum Degree Five are Subhamiltonian"
  with Boris Klemz.
  Appeared in Proc. 27th European Sympos. Algorithms (ESA '19), Leibniz Internat. Proc. Informatics (LIPIcs), Volume 144, München, Germany, 2019, 58:1–58:14.
  
  
• "An Improved Searching Algorithm on a Line by Four Truthful Robots and Two Byzantine Robots" (PDF)
  with Malte Milatz, Yoshio Okamoto, and Manuel Wettstein.
  Appeared in Abstracts 22nd Japan Conf. Discrete Comput. Geom. Graphs (JCDCG3 '19), Tokyo, Japan, 2019, 69–70.
  
  
• "Simultaneous Embeddings with Few Bends and Crossings"
  with Fabrizio Frati and Vincent Kusters.
  Appeared in Journal of Graph Algorithms and Applications, Volume 23(4), 2019, 683–713.
  
  
• "Green-Wins Solitaire Revisited–-Simultaneous Flips that Affect Many Edges"
  with János Pach and Miloš Stojaković.
  Appeared in Abstracts 35th European Workshop on Computational Geometry (EuroCG '19), Utrecht, Netherlands, 2019, 9:1–9:6.
  
  
• "Convex Hulls in Polygonal Domains"
  with Luis Barba, Matias Korman, and Alexander Pilz.
  Appeared in Proc. 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT '18), Leibniz Internat. Proc. Informatics (LIPIcs), Volume 101, Göteborg, Sweden, 2018, 8:1–8:13.
  
  
• "Arc diagrams, flip distances, and Hamiltonian triangulations"
  with Jean Cardinal, Vincent Kusters, Csaba D. Tóth, and Manuel Wettstein.
  Appeared in Computational Geometry: Theory and Applications, Volume 68, 2018, 206–225.
  Special issue in memory of Ferran Hurtado.
  
  
• "Minimal Geometric Graph Representations of Order Types"
  with Oswin Aichholzer, Martin Balko, Jan Kynčl, Wolfgang Mulzer, Irene Parada, Alexander Pilz, Manfred Scheucher, Pavel Valtr, Birgit Vogtenhuber, and Emo Welzl.
  Appeared in Abstracts 34th European Workshop on Computational Geometry (EuroCG '18), Berlin, Germany, 2018, 21:1–21:6.
  
  
• "Two Computational Geometry Libraries: LEDA and CGAL"
  with Lutz Kettner and Stefan Näher.
  Appeared in Handbook of Discrete and Computational Geometry, 2017, 1799–1832.
  
  
• "Netrunner Mate-in-1 or -2 is Weakly NP-Hard"
  with Jeffrey Bosboom.
  Appeared in CoRR, Volume abs/1710.05121, 2017.
  
  
• "Column Planarity and Partially-Simultaneous Geometric Embedding"
  with Luis Barba, William Evans, Vincent Kusters, Maria Saumell, and Bettina Speckmann.
  Appeared in Journal of Graph Algorithms and Applications, Volume 21(6), 2017, 983–1002.
  
  
• "Computing Nonsimple Polygons of Minimum Perimeter"
  with Sándor P. Fekete, Andreas Haas, Michael Hemmer, Irina Kostitsyna, Dominik Krupke, Florian Maurer, Joseph S. B. Mitchell, Arne Schmidt, Christiane Schmidt, and Julian Troegel.
  Appeared in Journal of Computational Geometry, Volume 8(1), 2017, 340–365.
  
  
• "Two-Planar Graphs Are Quasiplanar"
  with Csaba D. Tóth.
  Appeared in Proc. 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS '17), Leibniz Internat. Proc. Informatics (LIPIcs), Volume 83, Aalborg, Denmark, 2017, 47:1–47:14.
  
  
• "The Planar Tree Packing Theorem"
  with Markus Geyer, Michael Kaufmann, Vincent Kusters, and Csaba D. Tóth.
  Appeared in Journal of Computational Geometry, Volume 8(2), 2017, 109–177.
  
  
• "Obedient Plane Drawings for Disk Intersection Graphs"
  with Bahareh Banyassady, Boris Klemz, Maarten Löffler, and Tillmann Miltzow.
  Appeared in Proc. 15th Algorithms and Data Structures Symposium (WADS '17), Lecture Notes in Computer Science, Volume 10389, St. John’s (NL), Canada, 2017, 73–84.
  
  
• "The Planar Tree Packing Theorem"
  with Markus Geyer, Michael Kaufmann, Vincent Kusters, and Csaba D. Tóth.
  Appeared in Proc. 32nd International Symposium on Computational Geometry (SoCG '16), Leibniz Internat. Proc. Informatics (LIPIcs), Volume 51, Boston, USA, 2016, 41:1–41:15.
  
  
• "Computing Nonsimple Polygons of Minimum Perimeter"
  with Sándor P. Fekete, Andreas Haas, Michael Hemmer, Irina Kostitsyna, Dominik Krupke, Florian Maurer, Joseph S. B. Mitchell, Arne Schmidt, Christiane Schmidt, and Julian Troegel.
  Appeared in Proc. 15th Sympos. Experimental Algorithms (SEA '16), Lecture Notes in Computer Science, Volume 9685, St. Petersburg, Russia, 2016, 134–149.
  
  
• "An Improved Bound for Orthogeodesic Point Set Embeddings of Trees" (PDF)
  with Imre Bárány, Kevin Buchin, and Anita Liebenau.
  Appeared in Abstracts 32nd European Workshop on Computational Geometry (EuroCG '16), Lugano, Switzerland, 2016, 47–50.
  
  
• "On Universal Point Sets for Planar Graphs"
  with Jean Cardinal and Vincent Kusters.
  Appeared in Journal of Graph Algorithms and Applications, Volume 19(1), 2015, 529–547.
  
  
• "Simultaneous Embeddings with Few Bends and Crossings"
  with Fabrizio Frati and Vincent Kusters.
  Appeared in Proc. 23rd International Symposium on Graph Drawing & Network Visualization (GD '15), Lecture Notes in Computer Science, Volume 9411, Los Angeles, USA, 2015, 166–179.
  
  
• "Single-Player and Two-Player Buttons & Scissors Games"
  with Kyle Burke, Erik D. Demaine, Harrison Gregg, Robert A. Hearn, Adam Hesterberg, Hiro Ito, Irina Kostitsyna, Jody Leonard, Maarten Löffler, Aaron Santiago, Christiane Schmidt, Ryuhei Uehara, Yushi Uno, and Aaron Williams.
  Appeared in Proc. 18th Japan Conf. Discrete Comput. Geom. Graphs (JCDCGG '15), Lecture Notes in Computer Science, Volume 9943, Kyoto, Japan, 2015, 60–72.
  
  
• "Column Planarity and Partial Simultaneous Geometric Embedding for Outerplanar Graphs" (PDF)
  with Luis Barba and Vincent Kusters.
  Appeared in Abstracts 31st European Workshop on Computational Geometry (EuroCG '15), Ljubljana, Slovenia, 2015, 53–56.
  
  
• "Arc diagrams, flip distances, and Hamiltonian triangulations"
  with Jean Cardinal, Vincent Kusters, Csaba D. Tóth, and Manuel Wettstein.
  Appeared in Proc. 32nd Sympos. Theoret. Aspects Comput. Sci. (STACS '15), Leibniz Internat. Proc. Informatics (LIPIcs), Volume 30, München, Germany, 2015, 197–210.
  
  
• "Halving Balls in Deterministic Linear Time"
  with Vincent Kusters and Tillmann Miltzow.
  Appeared in Proc. 22nd European Sympos. Algorithms (ESA '14), Lecture Notes in Computer Science, Volume 8737, Wroclaw, Poland, 2014, 566–578.
  
  
• "Interference Minimization in Asymmetric Sensor Networks"
  with Yves Brise, Kevin Buchin, Dustin Eversmann, and Wolfgang Mulzer.
  Appeared in Proc. 10th Internat. Sympos. Algorithms and Experiments for Sensor Systems (ALGOSENSORS '14), Lecture Notes in Computer Science, Volume 8847, Wroclaw, Poland, 2014, 136–151.
  
  
• "Travel-time Maps: Linear Cartograms with Fixed Vertex Locations"
  with Kevin Buchin, Arthur van Goethem, Marc van Kreveld, and Bettina Speckmann.
  Appeared in Proc. 8th International Conference on Geographic Information Science (GIScience '14), Lecture Notes in Computer Science, Volume 8728, Vienna, Austria, 2014, 18–33.
  
  
• "Quality Ratios of Measures for Graph Drawing Styles"
  with Marc van Kreveld, Vincent Kusters, and Günter Rote.
  Appeared in Proc. 26th Canadian Conference on Computational Geometry (CCCG '14), Halifax (NS), Canada, 2014, 33–39.
  
  
• "Graph Drawings with Relative Edge Length Specifications"
  with Oswin Aichholzer, Marc van Kreveld, and Günter Rote.
  Appeared in Proc. 26th Canadian Conference on Computational Geometry (CCCG '14), Halifax (NS), Canada, 2014, 185–191.
  
  
• "Vertex-Colored Encompassing Graphs"
  with Csaba D. Tóth.
  Appeared in Graphs and Combinatorics, Volume 30(4), 2014, 933–947.
  
  
• "Covering Folded Shapes"
  with Oswin Aichholzer, Greg Aloupis, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Anna Lubiw, Jack Snoeyink, and Andrew Winslow.
  Appeared in Journal of Computational Geometry, Volume 5(1), 2014, 150–168.
  
  
• "Separating Balls with a Hyperplane"
  with Tillmann Miltzow and Vincent Kusters.
  Appeared in Abstracts 30th European Workshop on Computational Geometry (EuroCG '14), Ein-Gedi, Israel, 2014.
  
  
• "Plane Graphs with Parity Constraints"
  with Oswin Aichholzer, Thomas Hackl, Alexander Pilz, Günter Rote, Bettina Speckmann, and Birgit Vogtenhuber.
  Appeared in Graphs and Combinatorics, Volume 30(1), 2014, 47–69.
  
  
• "Convex Hull Alignment through Translation" (PDF)
  with Vincent Kusters, Günter Rote, Maria Saumell, and Rodrigo I. Silveira.
  Appeared in Proc. 25th Canadian Conference on Computational Geometry (CCCG '13), Waterloo (ON), Canada, 2013, 295–300.
  
  
• "Covering Folded Shapes" (PDF)
  with Oswin Aichholzer, Greg Aloupis, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Anna Lubiw, Jack Snoeyink, and Andrew Winslow.
  Appeared in Proc. 25th Canadian Conference on Computational Geometry (CCCG '13), Waterloo (ON), Canada, 2013, 73–78.
  
  
• "Planar Packing of Binary Trees"
  with Markus Geyer, Michael Kaufmann, Vincent Kusters, and Csaba D. Tóth.
  Appeared in Proc. 13th Algorithms and Data Structures Symposium (WADS '13), Lecture Notes in Computer Science, Volume 8037, London (ON), Canada, 2013, 353–364.
  
  
• "Coloring Hypergraphs Induced by Dynamic Point Sets and Bottomless Rectangles"
  with Andrei Asinowski, Jean Cardinal, Nathann Cohen, Sébastien Collette, Thomas Hackl, Kolja Knauer, Stefan Langerman, Michał Lasoń, Piotr Micek, Günter Rote, and Torsten Ueckerdt.
  Appeared in Proc. 13th Algorithms and Data Structures Symposium (WADS '13), Lecture Notes in Computer Science, Volume 8037, London (ON), Canada, 2013, 73–84.
  
  
• "Counting Plane Graphs: Flippability and Its Applications"
  with André Schulz, Micha Sharir, Adam Sheffer, Csaba D. Tóth, and Emo Welzl.
  Appeared in Thirty Essays on Geometric Graph Theory, 2013, 303–325.
  
  
• "On Universal Point Sets for Planar Graphs"
  with Jean Cardinal and Vincent Kusters.
  Appeared in Proc. Thailand-Japan Joint Conference on Computational Geometry and Graphs (TJJCCGG '12), Lecture Notes in Computer Science, Volume 8296, Bangkok, Thailand, 2013, 30–41.
  
  
• "Maximizing Maximal Angles for Plane Straight Line Graphs"
  with Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Attila Pór, Francisco Santos, Bettina Speckmann, and Birgit Vogtenhuber.
  Appeared in Computational Geometry: Theory and Applications, Volume 46(1), 2013, 17–28.
  
  
• "Maximum and Minimum against k lies"
  with Jiří Matoušek, Yoshio Okamoto, and Philipp Zumstein.
  Appeared in Chicago J. Theoretical Computer Science, Volume 2012, 2012, #2.
  
  
• "Coloring Dynamic Point Sets on a Line" (PDF)
  with Jean Cardinal, Nathann Cohen, Sébastien Collette, Stefan Langerman, and Günter Rote.
  Appeared in Abstracts 28th European Workshop on Computational Geometry (EuroCG '12), Assisi, Italy, 2012, 209–212.
  
  
• "Counting Plane Graphs: Flippability and Its Applications"
  with Micha Sharir, Adam Sheffer, Csaba D. Tóth, and Emo Welzl.
  Appeared in Proc. 12th Algorithms and Data Structures Symposium (WADS '11), Lecture Notes in Computer Science, Volume 6844, New York, U.S.A., 2011, 524–535.
  
  
• "Wireless Localization within Orthogonal Polyhedra"
  with Tobias Christ.
  Appeared in Proc. 23rd Canadian Conference on Computational Geometry (CCCG '11), Toronto (ON), Canada, 2011, 467–472.
  
  
• "The t-Pebbling Number is Eventually Linear in t"
  with Jiří Matoušek, Yoshio Okamoto, and Philipp Zumstein.
  Appeared in The Electronic Journal of Combinatorics, Volume 18(1), 2011, #P153.
  
  
• "Convex Partitions with 2-Edge Connected Dual Graphs"
  with Marwan Al Jubeh, Mashhood Ishaque, Diane L. Souvaine, and Csaba D. Tóth.
  Appeared in Journal of Combinatorial Optimization Volume 22(3), 2011, 409–425.
  
  
• "Maximum and Minimum against k lies"
  with Jiří Matoušek, Yoshio Okamoto, and Philipp Zumstein.
  Appeared in Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT '10), Lecture Notes in Computer Science, Volume 6139, Bergen, Norway, 2010, 139–149.
  
  
• "Improved Bounds for Wireless Localization"
  with Tobias Christ, Yoshio Okamoto, and Takeaki Uno.
  Appeared in Algorithmica, Volume 57(3), 2010, 499–516.
  
  
• "Pointed Binary Encompassing Trees: Simple and Optimal"
  with Bettina Speckmann and Csaba D. Tóth.
  Appeared in Computational Geometry: Theory and Applications, Volume 43(1), 2010, 35–41.
  
  
• "Plane Graphs with Parity Constraints"
  with Oswin Aichholzer, Thomas Hackl, Alexander Pilz, Günter Rote, Bettina Speckmann, and Birgit Vogtenhuber.
  Appeared in Proc. 11th Algorithms and Data Structures Symposium (WADS '09), Lecture Notes in Computer Science, Volume 5664, Banff(AB), Canada, 2009, 13–24.
  
  
• "Wireless Localization with Vertex Guards is NP-hard" (PDF)
  with Tobias Christ.
  Appeared in Proc. 21st Canadian Conference on Computational Geometry (CCCG '09), Vancouver (BC), Canada, 2009, 149–152.
  
  
• "Convex Partitions with 2-Edge Connected Dual Graphs"
  with Marwan Al Jubeh, Mashhood Ishaque, Diane L. Souvaine, and Csaba D. Tóth.
  Appeared in Proc. 15th Annual International Computing and Combinatorics Conference (COCOON '09), Lecture Notes in Computer Science, Volume 5609, Niagara Falls (NY), U.S.A., 2009, 192–204.
  
  
• "The Euclidean Degree-4 Minimum Spanning Tree Problem is NP-hard"
  with Andrea Francke.
  Appeared in Proc. 25th Annu. Sympos. Comput. Geom. (SoCG '09), Århus, Denmark, 2009, 179–188.
  
  
• "Natural Wireless Localization is NP-hard" (PDF)
  with Tobias Christ and Yoshio Okamoto.
  Appeared in Abstracts 25th European Workshop on Computational Geometry (EuroCG '09), Bruxelles, Belgium, 2009.
  
  
• "Improved Bounds for Wireless Localization"
  with Tobias Christ, Yoshio Okamoto, and Takeaki Uno.
  Appeared in Proc. 11th Scand. Workshop Algorithm Theory (SWAT '08), Lecture Notes in Computer Science, Volume 5124, Göteborg, Sweden, 2008, 77–89.
  
  
• "Disjoint Segments have Convex Partitions with 2-Edge Connected Dual Graphs" (PDF) (Gzipped Postscript) (Postscript)
  with Nadia Benbernou, Erik D. Demaine, Martin L. Demaine, Mashhood Ishaque, Diane L. Souvaine, and Csaba D. Tóth.
  Appeared in Proc. 19th Canadian Conference on Computational Geometry (CCCG '07), Ottawa, Canada, 2007, 13–16.
  (Erratum.)
  
  
• "Maximizing Maximal Angles for Plane Straight Line Graphs"
  with Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Attila Pór, Francisco Santos, Bettina Speckmann, and Birgit Vogtenhuber.
  Appeared in Proc. 10th Workshop Algorithms Data Struct. (WADS '07), Lecture Notes in Computer Science, Volume 4619, Halifax, Canada, 2007, 458–469.
  
  
• "An Adaptable and Extensible Geometry Kernel"
  with Susan Hert, Lutz Kettner, Sylvain Pion, and Michael Seel.
  Appeared in Computational Geometry: Theory and Applications, Volume 38(1–2), 2007, 16–36.
  
  
• "Maximizing Maximal Angles for Plane Straight Line Graphs" (PDF)
  with Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Francisco Santos, Bettina Speckmann, and Birgit Vogtenhuber.
  Appeared in Abstracts 23rd European Workshop on Computational Geometry (EuroCG '07), Graz, Austria, 2007, 98–101.
  
  
• "The Minimum Weight Triangulation Problem with few Inner Points"
  with Yoshio Okamoto.
  Appeared in Computational Geometry: Theory and Applications, Volume 34(3), 2006, 149–158.
  
  
• "Coloring Octrees"
  with Udo Adamy, József Solymosi, and Miloš Stojaković.
  Appeared in Theoretical Computer Science, Volume 363(1), 2006, 11–17.
  
  
• "Spanning Trees across Axis-Parallel Segments" (PDF) (Gzipped Postscript) (Postscript)
  with Csaba D. Tóth.
  Appeared in Proc. 18th Canadian Conference on Computational Geometry (CCCG '06), Kingston(ON), Canada, 2006, 101–104.
  
  
• "Chordless Paths Through Three Vertices"
  with Robert Haas.
  Appeared in Theoretical Computer Science, Volume 351(3), 2006, 360–371.
  
  
• "The Traveling Salesman Problem with Few Interior Points"
  with Vladimir Deĭneko, Yoshio Okamoto, and Gerhard Woeginger.
  Appeared in Operations Research Letters, Volume 34(1), 2006, 106–110.
  
  
• "A Simple Linear Algorithm for Computing Rectilinear 3-Centers"
  Appeared in Computational Geometry: Theory and Applications, Volume 31(3), 2005, 150–165.
  
  
• "Pointed and Colored Binary Encompassing Trees" (PDF) (Gzipped Postscript) (Postscript)
  with Csaba D. Tóth.
  Appeared in Proc. 21st Annu. Sympos. Comput. Geom. (SoCG '05), Pisa, Italy, 2005, 81–90.
  
  
• "Pointed Binary Encompassing Trees: Simple and Optimal" (PDF) (Gzipped Postscript) (Postscript)
  with Csaba D. Tóth.
  Appeared in Abstracts 21st European Workshop on Computational Geometry (EuroCG '05), Eindhoven, Netherlands, 2005, 93–96.
  
  
• "Pointed Binary Encompassing Trees: Simple and Optimal"
  with Csaba D. Tóth.
  Appeared in Abstracts 14th Annual Fall Workshop Comput. Geom., Cambridge (MA), USA, 2004, 28–29.
  Invited to a special issue of Computational Geometry: Theory and Applications.
  
  
• "Chordless Paths Through Three Vertices"
  with Robert Haas.
  Appeared in Proc. International Symposium on Parameterized and Exact Computation (IWPEC '04), Lecture Notes in Computer Science, Volume 3162, Bergen, Norway, 2004, 25–36.
  
  
• "The Minimum Weight Triangulation Problem with Few Interior Points"
  with Yoshio Okamoto.
  Appeared in Proc. International Symposium on Parameterized and Exact Computation (IWPEC '04), Lecture Notes in Computer Science, Volume 3162, Bergen, Norway, 2004, 200–212.
  
  
• "The Traveling Salesman Problem with Few Interior Points"
  with Vladimir Deĭneko, Yoshio Okamoto, and Gerhard Woeginger.
  Appeared in Proc. 10th Annual International Computing and Combinatorics Conference (COCOON '04), Lecture Notes in Computer Science, Volume 3106, Jeju Island, Korea, 2004, 268–277.
  
  
• "Coloring Octrees"
  with Udo Adamy, József Solymosi, and Miloš Stojaković.
  Appeared in Proc. 10th Annual International Computing and Combinatorics Conference (COCOON '04), Lecture Notes in Computer Science, Volume 3106, Jeju Island, Korea, 2004, 62–71.
  
  
• "Pointed Binary Encompassing Trees"
  with Bettina Speckmann and Csaba D. Tóth.
  Appeared in Proc. 9th Scand. Workshop Algorithm Theory (SWAT '04), Lecture Notes in Computer Science, Volume 3111, Humlebæk, Denmark, 2004, 442–454.
  
  
• "PushPush-k is PSPACE-Complete" (Gzipped Postscript) (Postscript)
  with Erik D. Demaine and Markus Holzer.
  Appeared in Proc. 3rd Internat. Conf. Fun with Algorithms (FUN '04), Isola d'Elba, Tuscany, Italy, 2004, 159–170.
  Preprint.
  
  
• "New Nomogram for Foetal Weight Estimation based on Hadlock's Two-parameter Formula"
  with Giordana M. Beutler, Juozas Kurmanavicius, Emo Welzl, Renate Huch, and Michael Bajka.
  Appeared in Ultraschall in der Medizin, Volume 25(1), 2004, 58–64.
  
  
• "Pointed Binary Encompassing Trees" (PDF) (Gzipped Postscript) (Postscript)
  with Bettina Speckmann and Csaba D. Tóth.
  Appeared in Abstracts 20th European Workshop on Computational Geometry (EuroCG '04), Seville, Spain, 2004, 131–134.
  
  
• "Alternating Paths through Disjoint Line Segments"
  with Csaba D. Tóth.
  Appeared in Information Processing Letters, Volume 87(6), 2003, 287–294.
  
  
• "Degree Bounds for Constrained Pseudo-Triangulations" (PDF) (Gzipped Postscript) (Postscript)
  with Oswin Aichholzer, Bettina Speckmann, and Csaba D. Tóth.
  Appeared in Proc. 15th Canadian Conference on Computational Geometry (CCCG '03), Halifax(NS), Canada, 2003, 155–158.
  
  
• "Pushing Blocks is Hard"
  with Erik D. Demaine, Martin L. Demaine, and Joseph O'Rourke.
  Appeared in Computational Geometry: Theory and Applications, Volume 26(1), 2003, 21–36.
  
  
• "Segment Endpoint Visibility Graphs are Hamiltonian"
  with Csaba D. Tóth.
  Appeared in Computational Geometry: Theory and Applications, Volume 26(1), 2003, 47–68.
  
  
• "Push-2F is PSPACE-Complete" (PDF) (Gzipped Postscript) (Postscript)
  with Erik D. Demaine and Robert A. Hearn.
  Appeared in Proc. 14th Canadian Conference on Computational Geometry (CCCG '02), Lethbridge(AB), Canada, 2002, 31–35.
  
  
• "Connecting Points in the Presence of Obstacles in the Plane" (PDF) (Gzipped Postscript) (Postscript)
  with Csaba D. Tóth.
  Appeared in Proc. 14th Canadian Conference on Computational Geometry (CCCG '02), Lethbridge(AB), Canada, 2002, 63–67.
  
  
• "Alternating Paths through Disjoint Line Segments" (PDF) (Gzipped Postscript) (Postscript)
  with Csaba D. Tóth.
  Appeared in Abstracts 18th European Workshop on Computational Geometry (EuroCG '02), Warsaw, 2002, 23–26.
  This is a revised and extended version.
  
  
• "An Adaptable and Extensible Geometry Kernel" (PDF) (Gzipped Postscript) (Postscript)
  with Susan Hert, Lutz Kettner, Sylvain Pion, and Michael Seel.
  Technical Report, Number 362, Institute for Theoretical Computer Science, ETH Zürich, September, 2001.
  Also appeared as MPI-I-2001-1-004 and INRIA RR-4270.
  
  
• "An Adaptable and Extensible Geometry Kernel"
  with Susan Hert, Lutz Kettner, Sylvain Pion, and Michael Seel.
  Appeared in Proc. 5th Workshop on Algorithm Engineering (WAE '01), Lecture Notes in Computer Science, Volume 2141, Århus, Denmark, August, 2001, 76–91.
  
  
• "Segment Endpoint Visibility Graphs are Hamiltonian" (PDF) (Gzipped Postscript) (Postscript)
  with Csaba D. Tóth.
  Appeared in Proc. 13th Canadian Conference on Computational Geometry (CCCG '01), Waterloo(ON), Canada, 2001, 109–112.
  Invited to a special issue of Computational Geometry: Theory and Applications.
  
  
• "Pushing Blocks is NP-complete for Noncrossing Solution Paths" (PDF) (Gzipped Postscript) (Postscript)
  with Erik D. Demaine.
  Appeared in Proc. 13th Canadian Conference on Computational Geometry (CCCG '01), Waterloo(ON), Canada, 2001, 65–68.
  Invited to a special issue of Computational Geometry: Theory and Applications.
  
  
• "Covering Polygons with Few Rectangles" (PDF) (Gzipped Postscript) (Postscript)
  Appeared in Abstracts 17th European Workshop on Computational Geometry (EuroCG '01), Berlin, 2001, 39–42.
  
  
• "Push-* is NP-hard" (PDF) (Gzipped Postscript) (Postscript)
  Appeared in Proc. 12th Canadian Conference on Computational Geometry (CCCG '00), Fredericton(NB), Canada, 2000, 205–210.
  
  
• "A Simple Linear Algorithm for Computing Rectangular Three-Centers" (PDF) (Gzipped Postscript) (Postscript)
  Appeared in Proc. 11th Canadian Conference on Computational Geometry (CCCG '99), Vancouver(BC), Canada, 1999, 72–75.
  Invited to a special issue of Computational Geometry: Theory and Applications.
  
  

Lecture Notes

The current version of our lecture notes on Geometry: Combinatorics and Algorithms are available at geometry.inf.ethz.ch.

Teaching

• Seminar Geometry: Combinatorics and Algorithms FS23
• Geometry: Combinatorics and Algorithms HS22
• Algorithms Lab HS22
• Seminar Geometry: Combinatorics and Algorithms FS22
• Geometry: Combinatorics and Algorithms HS21
• Algorithms Lab HS21
• Seminar Geometry: Combinatorics and Algorithms FS21
• Geometry: Combinatorics and Algorithms HS20
• Algorithms Lab HS20
• Seminar Geometry: Combinatorics and Algorithms FS20
• Geometry: Combinatorics and Algorithms HS19
• Algorithms Lab HS19
• Seminar Geometry: Combinatorics and Algorithms FS19
• Geometry: Combinatorics and Algorithms HS18
• Algorithms Lab HS18
• Seminar Geometry: Combinatorics and Algorithms FS18
• Geometry: Combinatorics and Algorithms HS17
• Algorithms Lab HS17
• Seminar Geometry: Combinatorics and Algorithms FS17
• Geometry: Combinatorics and Algorithms HS16
• Algorithms Lab HS16
• Seminar Geometry: Combinatorics and Algorithms FS16
• Geometry: Combinatorics and Algorithms HS15
• Algorithms Lab HS15
• Seminar Geometry: Combinatorics and Algorithms FS15
• Geometry: Combinatorics and Algorithms HS14
• Algorithms Lab HS14
• Computational Geometry HS13
• Seminar Computational Geometry and Geometric Graphs HS13
• Algorithms Lab HS13
• Geometric Graphs: Combinatorics and Algorithms FS13
• Computational Geometry HS12
• Seminar Computational Geometry and Graph Drawing HS12
• Algorithms Lab HS12
• Geometric Graphs: Combinatorics and Algorithms FS12
• Computational Geometry HS11
• Seminar Computational Geometry and Graph Drawing HS11
• Algorithms Lab HS11
• Graph Drawing FS11
• Computational Geometry HS10
• Algorithms Lab HS10
• Graph Drawing FS10
• Seminar Computational Geometry FS10
• Computational Geometry HS09
• Algorithms Lab HS09
• Seminar Computational Geometry FS09
• Computational Geometry HS08
• Seminar Computational Geometry FS08
• Computational Geometry HS07
• Seminar Computational Geometry HS07
• Computational Geometry WS06/07
• Seminar Computational Geometry WS06/07
• Computational Geometry WS05/06
• Seminar Computational Geometry WS05/06

Students

• Meghana M. Reddy, PhD (since Sep 2019), with Emo Welzl
• Nicolas Grelier, PhD 2022 (Maximum Clique in Generalisations of Disk Graphs and Plane Geometric Graphs on Degenerate Point Sets), with Emo Welzl
• Vincent Kusters, PhD 2015 (Simultaneous Embeddings), with Emo Welzl
• Tobias Christ, PhD 2011 (Discrete Descriptions of Geometric Objects), with Emo Welzl
• Bernhard Hilmarsson, Master CS 2023 (Minimum Coverage by Convex Polygons)
• Jela Kovacevic, Master CS 2022 (Universal geometric representations of graphs), with Nicolas Grelier
• Emanuel Seemann, Master Math. 2022 (Matchings and Hamiltonian circuits in 1-planar graphs), with Meghana M. Reddy
• Alain Bastian, Master CS 2022 (Minimum Partition into Plane Subgraphs), with Hung Hoang
• Alexandre Krattinger, Master CS 2022 (Edge-Coloring Simple Topological Drawings), with Meghana M. Reddy
• Alain Bastian, Semester Thesis 2021 (Edge coloring complete geometric graphs), with Meghana M. Reddy
• Ari Jordan, Bachelor Math. 2020 (Routing in Convex Partitions with Few Edges), with Nicolas Grelier
• Emanuel Seemann, Bachelor Math. 2019 (Monotone topological book embeddings of planar graphs with fixed spinal order), with Meghana M. Reddy
• Johannes Obenaus, Master CS 2019 (Spanning Trees with Low (Shallow) Stabbing Number), with Wolfgang Mulzer and Emo Welzl
• Wang Zeyu, Term Project Math. 2019 (Addition and Removal of Cycles in Vertex-transitive Graphs), with Patrick Schnider
• Giovanni Compagnoni, Master Math. 2019 (Combinatorial Flips for Hamiltonian Triangulations), with Hung Hoang
• Janis Nertinger, Master Math. 2019 (N Points and One Line Deterministically), with Hung Hoang
• Daniel Bertschinger, Term Project Math. 2018 (Nonstraight Drawings)
• Jela Kovacevic, Bachelor CS 2018 (Graceful Labelings of Trees: Flip Graphs and Further Properties), with Jerri Nummenpalo
• Anastasia Moskovaya, Master Math. 2017 (Different Tree Packing Conjectures), with János Pach
• Stefan Oancea, Bachelor CS 2017 (Exploring Graceful Labelings of Trees), with Jerri Nummenpalo
• Janis Nertinger, Bachelor Math 2016 (Book Embeddings of Planar Graphs)
• Jérôme Dohrau, Master CS 2015 (Edge Flips in Combinatorial Triangulations), with Vincent Kusters
• Stephan Ammann, Bachelor CS 2015 (Draw an outerplanar graph and a matching at the same time), with Vincent Kusters
• Patrick Schnider, Bachelor Math. 2014 (Shortest Paths in Disk Coverings), with Torsten Mütze
• Mikheil Amashukeli, Internship Project 2010 (Constrained Plane Graphs with Parity Constraints)
• Michèle Müller-Itten, Master Math. 2010 (Packing Rectangles into a Square), with Marek Sulovský
• Sabrina Wiedersheim, Master CS 2009 (Spiders and Snowflakes)
• Andrea Francke, Term Project CS 2009 (In Search of the Boundaries of Intractability for Euclidean Degree-k MST Problems)
• Aurosish Mishra, Internship Project 2009 (Wireless Vertex Guards), with Tobias Christ

Projects

• Arrangements and Drawings, Oct 2018 – Sep 2022
• GraDR IP3—Graph Drawings and Representations (EuroGIGA Project No. 10-EuroGIGA-OP-003), Sep 2011 – Aug 2014

Software

Community Service

• 40th International Symposium on Computational Geometry (SoCG 2024), Athens, Greece (June 10–14, 2024)
• 39th European Workshop on Computational Geometry (EuroCG 2023), Barcelona, Spain (Mar 29–31, 2023)
• 30th International Symposium on Graph Drawing and Network Visualization (GD 2022), Tokyo, Japan (Sep 13–16, 2022)
• 48th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2022), Tübingen, Germany (Jun 22–24, 2022)
• 37th European Workshop on Computational Geometry (EuroCG 2021), St. Petersburg, Russia (Apr 7–9, 2021)
• 31st Canadian Conference on Computational Geometry (CCCG 2019), Edmonton, Alberta (Aug 8–10, 2019)
• 35th European Workshop on Computational Geometry (EuroCG 2019), Utrecht, The Netherlands (Mar 18–20, 2019)
• 25th International Symposium on Graph Drawing & Network Visualization (GD 2017), Boston, U.S.A. (Sep 25–27, 2017)
• 33rd International Symposium on Computational Geometry (SoCG 2017), Brisbane, Australia (Jul 4–7, 2017)
• 33rd European Workshop on Computational Geometry (EuroCG 2017), Malmö, Sweden (Apr 5–7, 2017)
• 25th Multimedia Exposition in Computational Geometry at the 32nd International Symposium on Computational Geometry (SoCG 2016), Boston, U.S.A. (Jun 14–18, 2016)
• 32nd European Workshop on Computational Geometry (EuroCG 2016), Lugano, Switzerland (Mar 30–Apr 1, 2016)
• 30th European Workshop on Computational Geometry (EuroCG 2014), Ein-Gedi, Israel (Mar 3–5, 2014)
• 26th Canadian Conference on Computational Geometry (CCCG 2014), Halifax, Canada (Aug 11–13, 2014)
• Young Researchers Forum (YRF) at the 29th International Symposium on Computational Geometry (SoCG 2013), Rio de Janeiro, Brazil (Jun 17–20, 2013)
• 28th European Workshop on Computational Geometry (EuroCG 2012), Assisi, Italy (Mar 19–21, 2012)
• 16th Annual European Symposium on Algorithms (ESA 2008), Engineering and Applications Track, Karlsruhe, Germany, (Sep 15–19, 2008)

• 27th European Workshop on Computational Geometry (EuroCG 2011), Morschach, Switzerland (Mar 28–30, 2011)

• CGWeek 2020 with the 36th International Symposium on Computational Geometry (SoCG 2020), Zürich, Switzerland (June 22–26, 2020)
• 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), Zürich, Switzerland (Jul 4–8, 2011)
• ALGO 2006, Zürich, Switzerland (Sep 11–15, 2006)