Arrangements and Drawings (ArrDra)

This is the webpage of the Swiss team of the ArrDra project . The project ran from October 2018 to September 2022.
It was supported by the Swiss National Science Foundation as SNSF Project 200021E-171681.

People

The team consisted of the following people:

• Principal Investigator:
  - Michael Hoffmann


• Students:
  - Nicolas Grelier (October 2018 — July 2022)
  - Meghana M. Reddy (September 2019 — September 2022)


• Associate members:
  - Luis Barba (until August 2019)
  - Daniel Bertschinger (October 2019 — July 2022)
  - Hung Hoang (until August 2022)
  - Patrick Schnider (until September 2020)
  - Tim Taubner (September 2019 — October 2021)
  - Emo Welzl

• Apr 11-15, 2022: Seventh DACH Workshop, Wittenberg, Germany
• Aug 23-27, 2021: Sixth DACH Workshop, Stels (GR), Switzerland
• Feb 22-26, 2021: Fifth DACH Workshop, online
• Feb 24-28, 2020: Fourth DACH Workshop, Berlin
• Aug 19-23, 2019: Third DACH Workshop, Wergenstein (GR), Switzerland
• Jan 21-25, 2019: Second DACH Workshop, Graz, Austria
• Sep 10-13, 2018: First DACH Workshop, Tornow, Germany

Journal Publications and Peer-reviewed Conferences

• Boris Klemz and Kristin Knorr and Meghana M. Reddy and Felix Schröder:
  Simplifying Non-Simple Fan-Planar Drawings
  Appeared in Journal of Graph Algorithms and Applications 27:2 (2023), 147–172.
  A preliminary version appeared in Proc. 28th International Symposium on Graph Drawing & Network Visualization (GD 2021), LNCS 12868, 57–71.
  


• Oswin Aichholzer, Man-Kwun Chiu, Hung Hoang, Michael Hoffmann, Jan Kynčl, Yannic Maus, Birgit Vogtenhuber, and Alexandra Weinberger.
  Drawings of Complete Multipartite Graphs up to Triangle Flips
  Appeared in Proc. 38th International Symposium on Computational Geometry (SoCG 2023), LIPIcs 258, 6:1–6:16.
  Preliminary results were presented at the 38th European Workshop on Computational Geometry (EuroCG 2022).
  
  
• Fabrizio Frati, Michael Hoffmann and Csaba D. Tóth:
  Universal Geometric Graphs
  Appeared in Combinatorics, Probability and Computing 32:5 (2023),742–761.
  A preliminary version appeared in Proc. 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2020), LNCS Volume 12301, 174–186.
  


• Martin Balko, Steven Chaplick, Robert Ganian, Siddharth Gupta, Michael Hoffmann, Pavel Valtr, and Alexander Wolff:
  Bounding and Computing Obstacle Numbers of Graphs
  Appeared in Proc. 30th European Sympos. Algorithms (ESA 2022), LIPIcs 244, 11:1–11:13.
  
  
• Sergio Cabello, Michael Hoffmann, Katharina Klost, Wolfgang Mulzer, and Josef Tkadlec
  Long Plane Trees
  Appeared in Proc. 38th International Symposium on Computational Geometry (SoCG 2022), LIPIcs 224, 23:1–23:17.
  Preliminary results were presented at the 37th European Workshop on Computational Geometry (EuroCG 2021).
  
  
• Nicolas Grelier:
  Hardness and Approximation of Minimum Convex Partition
  Appeared in Proc. 38th International Symposium on Computational Geometry (SoCG 2022), LIPIcs 224, 45:1–45:15.
  
  
• Helena Bergold, Daniel Bertschinger, Nicolas Grelier, Wolfgang Mulzer and Patrick Schnider:
  Well-Separation and Hyperplane Transversals in High Dimensions
  Appeared in Proc. 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022), LIPIcs 227, 16:1–16:14.
  
  
• Daniel Bertschinger, Meghana M. Reddy and Enrico Mann:
  Lions and Contamination: Monotone Clearings
  Appeared in Proc. 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022), LIPIcs 227, 17:1–17:11.
  
  
• Jonas Cleve, Nicolas Grelier, Kristin Knorr, Maarten Löffler, Wolfgang Mulzer and Daniel Perz:
  Nearest-Neighbor Decompositions of Drawings
  Appeared in Proc. 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022), LIPIcs 227, 21:1–21:16.
  Preliminary results were presented at the 37th European Workshop on Computational Geometry (EuroCG 2021).
  
  
• Nicolas Grelier:
  Computing a maximum clique in geometric superclasses of disk graphs
  Appeared in Journal of Combinatorial Optimization 44 (2022), 3106-3135.
  A preliminary version appeared in Proc. 15th Annual International Computing and Combinatorics Conference (COCOON 2020), LNCS 12273, 299–310.


• Stefan Felsner, Michael Hoffmann, Kristin Knorr and Irene Parada:
  On the maximum number of crossings in star-simple drawings of K_n with no empty lens
  Appeared in Journal of Graph Algorithms and Applications 26:3 (2022), 353–361.
  A preliminary version appeared in Proc. 28th International Symposium on Graph Drawing & Network Visualization (GD 2020), LNCS 12590, 382–389.
  Preliminary results were presented at the 36th European Workshop on Computational Geometry (EuroCG 2020).
  


• Sabine Cornelsen, Maximilian Pfister, Henry Förster, Martin Gronemann, Michael Hoffmann, Stephen Kobourov and Thomas Schneck:
  Drawing Shortest Paths in Geodetic Graphs
  Appeared in Journal of Graph Algorithms and Applications 26:3 (2022), 353–361.
  A preliminary version appeared in Proc. 28th International Symposium on Graph Drawing & Network Visualization (GD 2020), LNCS 12590, 333–340.
  


• Andrey Kupavskii and Emo Welzl:
  Lower Bounds for Searching Robots, some Faulty
  Appeared in Distributed Computing Journal 34 (2021), 229–237.


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


• Édouard Bonnet, Nicolas Grelier and Tillmann Miltzow:
  Maximum Clique in Disk-Like Intersection Graphs
  40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020), LIPIcs 182, 17:1–17:18.


• Michael Hoffmann, Chih-Hung Liu, Csaba D. Tóth and Meghana M. Reddy:
  Simple Topological Drawings of k-Planar Graphs
  Appeared in Proc. 28th International Symposium on Graph Drawing & Network Visualization (GD 2020), LNCS 12590, 390–402.
  Preliminary results were presented at the 36th European Workshop on Computational Geometry (EuroCG 2020).


• Oswin Aichholzer, Michael Hoffmann, Johannes Obenaus, Rosna Paul, Daniel Perz, Nadja Seiferth, Birgit Vogtenhuber and Alexandra Weinberger:
  Plane Spanning Trees in Edge-Colored Simple Drawings of K_n
  Appeared in Proc. 28th International Symposium on Graph Drawing & Network Visualization (GD 2020), LNCS 12590, 482–489.
  


• Man-Kwun Chiu, Stefan Felsner, Manfred Scheucher, Patrick Schnider, Raphael Steiner and Pavel Valtr:
  On the Average Complexity of the k-Level
  Journal of Computational Geometry 11:1 (2020), 493–506.
  Preliminary results were presented at the 36th European Workshop on Computational Geometry (EuroCG 2020)
  


• Uli Wagner and Emo Welzl:
  Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips)
  Proc. 36th International Symposium on Computational Geometry (SoCG 2020), 67:1-67:16.


• Xavier Goaoc and Emo Welzl:
  Convex hulls of random order types
  Proc. 36th International Symposium on Computational Geometry (SoCG 2020), 49:1-49:15.


• Uli Wagner and Emo Welzl:
  Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips)
  31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), 2823-2841


• Patrizio Angelini, Henry Förster, Michael Hoffmann, Michael Kaufmann, Stephen Kobourov, Giuseppe Liotta and Maurizio Patrignani:
  The QuaSEFE Problem
  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.


• Oswin Aichholzer, Martin Balko, Michael Hoffmann, Jan Kynčl, Wolfgang Mulzer, Irene Parada, Alexander Pilz, Manfred Scheucher, Pavel Valtr, Birgit Vogtenhuber and Emo Welzl:
  Minimal Representations of Order Types by Geometric Graphs
  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.


• Nicolas Grelier, Rémi de Joannis de Verclos, Ross J. Kang and François Pirot:
  Approximate strong edge-colouring of unit disk graphs
  Appeared in Proc. 17th International Workshop on Approximation and Online Algorithms (WAOA 2019), Lecture Notes in Computer Science, Volume 11926, München, Germany, 2019, 154-169.


• Michael Hoffmann and Boris Klemz:
  Triconnected Planar Graphs of Maximum Degree Five are Subhamiltonian
  Appeared in Proc. 27th European Sympos. Algorithms (ESA '19), LIPIcs 144, 58:1–58:14.


• Michael Hoffmann, Malte Milatz, Yoshio Okamoto and Manuel Wettstein:
  An Improved Searching Algorithm on a Line by Four Truthful Robots and Two Byzantine Robots (PDF)
  Presented at the 22nd Japan Conf. Discrete Comput. Geom. Graphs (JCDCG3 '19), 69–70.


• Patrizio Angelini, Michael A. Bekos, Franz J. Brandenburg, Giordano Da Lozzo, Giuseppe Di Battista, Walter Didimo,Michael Hoffmann, Giuseppe Liotta, Fabrizio Montecchiani, Ignaz Rutter and Csaba D. Tóth:
  Simple k-Planar Graphs are Simple (k + 1)-Quasiplanar
  Appeared in J. Combin. Theory Ser. B, 142, 2020, 1-35.
  
  
• Fabrizio Frati, Michael Hoffmann and Vincent Kusters:
  Simultaneous Embeddings with Few Bends and Crossings
  Appeared in Journal of Graph Algorithms and Applications, Volume 23(4), 2019, 683–713.

Other

• Fabian Klute, Meghana M. Reddy and Tillmann Miltzow:
  Local Complexity of Polygons
  Presented at the 37th European Workshop on Computational Geometry (EuroCG 2021)
  


• Steven Chaplick, Henry Förster, Michael Hoffmann and Michael Kaufmann:
  Monotone Arc Diagrams with few Biarcs
  Presented at the 36th European Workshop on Computational Geometry (EuroCG 2020)
  


• Sergio Cabello, Aruni Choudhary, Michael Hoffmann, Katharina Klost, Meghana M. Reddy, Wolfgang Mulzer, Felix Schröder and Josef Tkadlec:
  A better approximation for longest noncrossing spanning trees
  Presented at the 36th European Workshop on Computational Geometry (EuroCG 2020)
  


• Nicolas Grelier:
  Minimum Convex Partition of Degenerate Point Sets is NP-Hard
  Presented at the 36th European Workshop on Computational Geometry (EuroCG 2020)
  


• Michael Hoffmann, János Pach and Miloš Stojaković:
  Green-Wins Solitaire Revisited-Simultaneous Flips that Affect Many Edges
  Appeared in Abstracts 35th European Workshop on Computational Geometry (EuroCG '19), Utrecht, Netherlands, 2019