Publications

  • Hamiltonian meander paths and cycles on bichromatic point sets
    Oswin Aichholzer, Carlos Alegría Galicia, Irene Parada, Alexander Pilz, Javier Tejel, Csaba D. Tóth, Jorge Urrutia, and Birgit Vogtenhuber
    In the Proceedings of XVIII Encuentros de Geometría Computacional, pages 35--38, 2019. [url]
  • Transformed flips in triangulations and matchings
    Oswin Aichholzer, Lukas Andritsch, Karin Baur, and Birgit Vogtenhuber
    Submitted.
    [arXiv:1907.08758]
  • A superlinear lower bound on the number of 5-holes
    Oswin Aichholzer, Martin Balko, Thomas Hackl, Jan Kynčl, Irene Parada, Manfred Scheucher, Pavel Valtr, and Birgit Vogtenhuber
    Full version to appear in the Journal of Combinatorial Theory, Series A.
    In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG 2017), pages 8:1--8:16, LIPIcs 77, Dagstuhl, 2017. [doi]
    Extended Abstract in Proceedings of the 33rd European Workshop on Computational Geometry (EuroCG), 2017. [url]
    [arXiv:1703.05253]
  • Minimal Geometric Graph Representations of Order Types
    Oswin Aichholzer, Martin Balko, Michael Hoffmann, Jan Kynčl, Wolfgang Mulzer, Irene Parada, Alexander Pilz, Manfred Scheucher, Pavel Valtr, Birgit Vogtenhuber, and Emo Welzl.
    To appear in the Proceedings of 27th International Symposium on Graph Drawing and Network Visualization (GD 2019).
    Extended Abstract in Proceedings of the 34th European Workshop on Computational Geometry (EuroCG), 2018. [url]
    [arXiv:1908.05124]
  • Flip distances between graph orientations
    Oswin Aichholzer, Jean Cardinal, Tony Huynh, Kolja Knauer, Torsten Mütze, Raphael Steiner, and Birgit Vogtenhuber
    Full version submitted to journal.
    To appear in the Proceedings of 45th International Workshop on Graph-Theoretic Concepts in Computer Science.
    [arXiv:1902.06103]
  • Erdős-Szekeres-Type Games
    Oswin Aichholzer, José-Miguel Díaz-Báñez, Thomas Hackl, David Orden, Alexander Pilz, Inmaculada Ventura, and Birgit Vogtenhuber
    Extended Abstract in Proceedings of the 35th European Workshop on Computational Geometry (EuroCG), 2019. [url]
  • An Ongoing Project to Improve the Rectilinear and the Pseudolinear Crossing Constants
    Oswin Aichholzer, Frank Duque, Ruy Fabila-Monroy, Carlos Hidalgo-Toscano, and Oscar E. García-Quintero
    Submitted.
    [arXiv:1907.07796]
  • On the 2-Colored Crossing Number
    Oswin Aichholzer, Ruy Fabila-Monroy, Adrian Fuchs, Carlos Hidalgo Toscano, Irene Parada, Birgit Vogtenhuber, and Francisco Zaragoza
    To appear in the Proceedings of 27th International Symposium on Graph Drawing and Network Visualization (GD 2019).
    Extended Abstract in Proceedings of the 35th European Workshop on Computational Geometry (EuroCG), 2019. [url]
    [arXiv:1908.06461]
  • On the Triangle Vector
    Oswin Aichholzer, Ruy Fabila-Monroy, and Julia Obmann
    In the Proceedings of XVIII Encuentros de Geometría Computacional, pages 55--58, 2019. [url]
  • Graphs with large total angular resolution
    Oswin Aichholzer, Matias Korman, Yoshio Okamoto, Irene Parada, Daniel Perz, Andre van Renssen, and Birgit Vogtenhuber
    To appear in the Proceedings of 27th International Symposium on Graph Drawing and Network Visualization (GD 2019).
    Extended Abstract in Proceedings of the 35th European Workshop on Computational Geometry (EuroCG), 2019. [url]
    [arXiv:1908.08857]
  • NP-Completeness of Max-Cut for Segment Intersection Graphs
    Oswin Aichholzer, Wolfgang Mulzer, Patrick Schnider, and Birgit Vogtenhuber
    Extended Abstract in Proceedings of the 34th European Workshop on Computational Geometry (EuroCG), 2018. [url]
  • Shooting Stars in Simple Drawings of $K_{m,n}$
    Oswin Aichholzer, Irene Parada, Manfred Scheucher, Birgit Vogtenhuber, and Alexandra Weinberger
    Extended Abstract in Proceedings of the 35th European Workshop on Computational Geometry (EuroCG), 2019. [url]
  • Triangles in the colored Euclidean plane
    Oswin Aichholzer and Daniel Perz
    Extended Abstract in Proceedings of the 35th European Workshop on Computational Geometry (EuroCG), 2019. [url]
  • Packing 2D Disks into a 3D Container
    Helmut Alt, Otfried Cheong, Ji-won Park, and Nadja Scharf
    In Proceedings of the 13th International Conference on Algorithms and Computation (WALCOM), pages 369--380, LNCS 11355, Springer, 2019. [doi]
    Extended Abstract in Proceedings of the 34th European Workshop on Computational Geometry (EuroCG), 2018. [url]
  • Approximating Smallest Containers for Packing Three-Dimensional Convex Objects
    Helmut Alt and Nadja Scharf
    International Journal of Computational Geometry and Applications, 28(2):111--128, 2018. [doi]
  • Simple $k$-Planar Graphs are Simple $(k + 1)$-Quasiplanar
    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
    Full version to appear in the Journal of Combinatorial Theory, Series B. [doi]
  • The QuaSEFE Problem
    Patrizio Angelini, Henry Förster, Michael Hoffmann, Michael Kaufmann, Stephen Kobourov, Giuseppe Liotta, and Maurizio Patrignani
    To appear in the Proceedings of 27th International Symposium on Graph Drawing and Network Visualization (GD 2019).
    [arXiv:1908.08708]
  • Asymmetric Convex Intersection Testing
    Luis Barba and Wolfgang Mulzer
    In Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA 2019) pages 9:1--9:14, OASIcs 69, Dagstuhl, 2019. [doi]
    [arXiv:1808.06460]
  • Line and Plane Cover Numbers Revisited
    Therese C. Biedl, Stefan Felsner, Henk Meijer, and Alexander Wolff
    To appear in the Proceedings of 27th International Symposium on Graph Drawing and Network Visualization (GD 2019).
    [arXiv:1908.07647]
  • On the Maximum Crossing Number
    Markus Chimani, Stefan Felsner, Stephen G. Kobourov, Torsten Ueckerdt, Pavel Valtr, and Alexander Wolff
    Journal of Graph Algorithms and Applications, 22:67--87, 2018. [url]
  • Recognizing Embedded Caterpillars with Weak Unit Disk Contact Representations is NP-hard
    Man-Kwun Chiu, Jonas Cleve, and Martin Nöllenburg
    Extended Abstract in Proceedings of the 35th European Workshop on Computational Geometry (EuroCG), 2019. [url]
  • On orthogonal symmetric chain decompositions.
    Karl Däubel, Sven Jäger, Torsten Mütze, and Manfred Scheucher
    Full version in the Electronic Journal of Combinatorics 26(3), Research paper P3.64, 32 pages, 2019. [url]
    Short version in Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB 2019), Acta Mathematica Universitatis Comenianae 88(3), pages 611--618, 2019. [url]
    [arXiv:1810.09847]
  • 4-Connected Triangulations on Few Lines.
    Stefan Felsner
    To appear in the Proceedings of 27th International Symposium on Graph Drawing and Network Visualization (GD 2019).
    [arXiv:1908.04524]
  • Pseudoline Arrangements
    Stefan Felsner and Jacob E. Goodman
    Chapter 5 in Handbook of Discrete and Computational Geometry 3rd edition, CRC Press 2017. [url]
  • Rainbow cycles in flip graphs
    Stefan Felsner, Linda Kleist, Torsten Mütze, and Leon Sering
    Proceedings SoCG, volume 99 of LIPIcs, pages 38:1--38:14, Schloss Dagstuhl, 2018. [doi]
  • Arrangements of Approaching Pseudo-Lines
    Stefan Felsner and Alexander Pilz
    Proceedings EuroCG 17. [url]
  • Arrangements of Pseudocircles: Triangles and Drawings
    Stefan Felsner and Manfred Scheucher
    Full version to appear in Discrete & Computational Geometry (DCG).
    In Proceedings of 25th International Symposium on Graph Drawing and Network Visualization (GD 2017), pages 127--139, LNCS 10692, Springer, 2017. [doi]
    Extended Abstract in Proceedings of the 33rd European Workshop on Computational Geometry (EuroCG), 2017. [url]
    [arXiv:1708.06449]
  • Arrangements of Pseudocircles: On Circularizability
    Stefan Felsner and Manfred Scheucher
    Full version to appear in Discrete & Computational Geometry, Ricky Pollack Memorial Issue (DCG). [doi]
    In the Proceedings of 26th International Symposium on Graph Drawing and Network Visualization (GD 2018), pages 555--568, LNCS 11282, Springer, 2018. [doi]
    Extended Abstract in Proceedings of the 34th European Workshop on Computational Geometry (EuroCG), 2018. [url]
    [arXiv:1712.02149]
  • Perfect rainbow polygons for colored point sets in the plane
    David Flores-Peñaloza, Mikio Kano, Leonardo Martínez-Sandoval, David Orden, Javier Tejel, Csaba D. Tóth, Jorge Urrutia, and Birgit Vogtenhuber
    In the Proceedings of XVIII Encuentros de Geometría Computacional, pages 43--46, 2019. [url]
    In the Proceedings of 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG3 2019), pages 57--58, 2019. [url]
  • Simultaneous Embeddings with Few Bends and Crossings
    Fabrizio Frati, Michael Hoffmann, and Vincent Kusters
    Appeared in Journal of Graph Algorithms and Applications, Volume 23(4), 2019, 683--713. [url]
  • A unifying framework for maximum clique on $(d-1)$-ball and unit d-ball graphs
    Nicolas Grelier
    Manucript in preparation
  • On the VC-dimension of convex sets and half-spaces
    Nicolas Grelier, Saeed Gh. Ilchi, Tillmann Miltzow, and Shakhar Smorodinsky
    Submitted.
    [arXiv:1907.01241]
  • Approximate strong edge-colouring of unit disk graphs
    Nicolas Grelier, Rémi de Joannis de Verclos, Ross J. Kang, and François Pirot
    Presented at WAOA 2019.
    Extended Abstract in Proceedings of the 35th European Workshop on Computational Geometry (EuroCG), 2019. [url]
  • Triconnected Planar Graphs of Maximum Degree Five are Subhamiltonian
    Michael Hoffmann and 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. [doi]
  • An Improved Searching Algorithm on a Line by Four Truthful Robots and Two Byzantine Robots
    Michael Hoffmann, Malte Milatz, Yoshio Okamoto, and Manuel Wettstein
    Appeared in Abstracts 22nd Japan Conf. Discrete Comput. Geom. Graphs (JCDCG3 '19), Tokyo, Japan, 2019, 69--70. [url]
  • Green-Wins Solitaire Revisited-Simultaneous Flips that Affect Many Edges
    Michael Hoffmann, János Pach, and Miloš Stojaković
    Extended Abstract in Proceedings of the 35th European Workshop on Computational Geometry (EuroCG), 2019. [url]
  • Bounding the number of crossings for a particular class of drawings of $K_{n,n}$
    Carolina Medina, Irene Parada, Gelasio Salazar, and Birgit Vogtenhuber
    In the Proceedings of XVIII Encuentros de Geometría Computacional, page 34, 2019. [url]
  • On L-shaped Point Set Embeddings of Trees: First Non-embeddable Examples
    Torsten Mütze and Manfred Scheucher
    In the Proceedings of 26th International Symposium on Graph Drawing and Network Visualization (GD 2018), pages 354--360, LNCS 11282, Springer, 2018. [doi]
    [arXiv:1807.11043]
  • On Disjoint Holes in Point Sets
    Manfred Scheucher
    Extended Abstract in Proceedings of the 35th European Workshop on Computational Geometry (EuroCG), 2019. [url]
    Short version in Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB 2019), Acta Mathematica Universitatis Comenianae 88(3), pages 1049--1056, 2019. [url]
    [arXiv:1807.10848]
  • A Note On Universal Point Sets for Planar Graphs
    Manfred Scheucher, Hendrik Schrezenmaier, and Raphael Steiner
    To appear in the Proceedings of 27th International Symposium on Graph Drawing and Network Visualization (GD 2019).
    Extended Abstract in Proceedings of the 35th European Workshop on Computational Geometry (EuroCG), 2019. [url]
    [arXiv:1811.06482]
  • Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips)
    Uli Wagner and Emo Welzl
    To appear in the Proceedings of 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020).