Dr. Manfred Scheucher

Publications and Preprints

1. Using SAT to find NP-hardness proofs for 41 completion problems
   with Helena Bergold and Felix Schröder.
   In preparation.
2. SAT-Based Generation of Planar Graphs
   with Markus Kirchweger and Stefan Szeider.
   To appear in the Proceedings of the 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023), 2023+.
3. Roudneff's Conjecture in Dimension $4$
   with Rangel Hernández-Ortiz, Kolja Knauer, and Luis Pedro Montejano.
   To appear in the Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB 2023), 2023+.
   Preprint available at [arXiv:2303.14212]
4. Bichromatic Perfect Matchings with Crossings
   with Oswin Aichholzer, Stefan Felsner, Rosna Paul, and Birgit Vogtenhuber.
   Extended abstract in the Proceedings of the 39th European Workshop on Computational Geometry (EuroCG), 2023. [url] [pdf]
5. Holes in convex drawings
   with Helena Bergold and Felix Schröder.
   Extended abstract in the Proceedings of the 39th European Workshop on Computational Geometry (EuroCG), 2023. [url] [pdf]
6. Flip Graphs for Arrangements of Pseudocircles
   with Stefan Felsner, Johannes Obenaus, Sandro Roch and Birgit Vogtenhuber.
   Extended abstract in the Proceedings of the 39th European Workshop on Computational Geometry (EuroCG), 2023. [url] [pdf]
7. Using SAT to study plane Hamiltonian substructures in simple drawings
   with Helena Bergold, Stefan Felsner and Meghana M. Reddy.
   Extended abstract in the Proceedings of the 39th European Workshop on Computational Geometry (EuroCG), 2023. [url] [pdf]
   Preprint available at [arXiv:2305.09432]
8. A SAT Attack on Rota's Basis Conjecture
   with Markus Kirchweger and Stefan Szeider.
   In Proceedings of the 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022), 4:1--4:18, LIPIcs 236, Schloss Dagstuhl, 2022. [doi]
   [supplemental data]
9. An extension theorem for signotopes
   with Helena Bergold and Stefan Felsner.
   To appear in Proceedings of the 39th International Symposium on Computational Geometry (SoCG 2023).
   Preprint available at [arXiv:2303.04079]
   [supplemental data]
10. Arrangements of Pseudocircles: On Digons and Triangles
    with Stefan Felsner and Sandro Roch.
    In Proceedings of 28th International Symposium on Graph Drawing and Network Visualization (GD 2022), pages 441--455, LNCS 13764, Springer, 2023. [doi]
    Preprint available at [arXiv:2208.12110]
11. Blocking Delaunay Triangulations from the Exterior
    with Oswin Aichholzer, Thomas Hackl, Maarten Löffler, Alexander Pilz, Irene Parada, and Birgit Vogtenhuber.
    In Proceedings of the 38th European Workshop on Computational Geometry (EuroCG), 2022. [url] [pdf]
    Preprint available at [arXiv:2210.12015]
12. Erdős--Szekeres-type problems in the real projective plane
    with Martin Balko and Pavel Valtr.
    In Proceedings of the 38th International Symposium on Computational Geometry (SoCG 2022), pages 10:1--10:15, LIPIcs 224, Schloss Dagstuhl, 2022. [doi]
    Preprint available at [arXiv:2203.07518]
13. A SAT attack on Erdős--Szekeres numbers in R^d and the Empty Hexagon Theorem
    Manfred Scheucher.
    In Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB 2021), pages 103--110, TM 14, Springer, 2021. [doi]
    In Computing in Geometry and Topology 2(1), 2:1--2:13, 2023. [doi] [arXiv:2105.08406]
    [supplemental data]
14. Tight bounds on the expected number of holes in random point sets
    with Martin Balko and Pavel Valtr.
    In Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB 2021), pages 411--416, TM 14, Springer, 2021. [doi]
    In Random Structures & Algorithms 62(1), pages 29--51, 2022. [doi] [arXiv:2111.12533]
15. Coloring Circle Arrangements: New 4-Vertex-Critical Planar Graphs
    with Man-Kwun Chiu, Stefan Felsner, Felix Schröder, Raphael Steiner, and Birgit Vogtenhuber.
    In Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB 2021), pages 84--91, TM 14, Springer, 2021. [doi]
    Full version accepted in the European Journal of Combinatorics, special issue of EuroComb21. [arXiv:2205.08181]
16. On Crossing-Families in Planar Point Sets
    with Oswin Aichholzer, Jan Kynčl, Pavel Valtr, and Birgit Vogtenhuber.
    In Computational Geometry: Theory and Applications 107, 2022. Special Issue EuroCG 2021. [doi] [arXiv:2109.10705]
17. Many Order Types on Integer Grids of Polynomial Size
    Manfred Scheucher.
    In Computational Geometry: Theory and Applications 109, 2023. Special Issue EuroCG 2021. [doi] [arXiv:2007.15334]
18. Topological Drawings meet Classical Theorems from Convex Geometry
    with Helena Bergold, Stefan Felsner, Felix Schröder, and Raphael Steiner.
    In Proceedings of 28th International Symposium on Graph Drawing and Network Visualization (GD 2020), pages 281--294, LNCS 12590, Springer, 2020. [doi]
    In Discrete & Computational Geometry, 2022. [doi] [arXiv:2005.12568]
19. Holes and islands in random point sets
    with Martin Balko and Pavel Valtr.
    In Proceedings of the 36th International Symposium on Computational Geometry (SoCG 2020), pages 14:1--14:16, LIPIcs 164, Schloss Dagstuhl, 2020. [doi]
    In Random Structures & Algorithms, 2021. [doi] [arXiv:2003.00909]
20. On the Average Complexity of the $k$-Level
    with Man-Kwun Chiu, Stefan Felsner, Patrick Schnider, Raphael Steiner, and Pavel Valtr.
    In Journal of Computational Geometry 11(1), pages 493--506, 2020. [doi] [arXiv:1911.02408]
21. Shooting Stars in Simple Drawings of $K_{m,n}$
    with Oswin Aichholzer, Irene Parada, Birgit Vogtenhuber, and Alexandra Weinberger.
    In Proceedings of the 35th European Workshop on Computational Geometry (EuroCG), pages 59:1--59:6, 2019. [url] [pdf]
22. A Note On Universal Point Sets for Planar Graphs
    with Hendrik Schrezenmaier and Raphael Steiner.
    In Proceedings of 27th International Symposium on Graph Drawing and Network Visualization (GD 2019), pages 350--362, LNCS 11904, Springer 2019. [doi]
    In Journal of Graph Algorithms and Applications 24(3), pages 171--190, 2020. [doi] [arXiv:1811.06482]
    [supplemental data]
23. On orthogonal symmetric chain decompositions
    with Karl Däubel, Sven Jäger and Torsten Mütze.
    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] [pdf]
    In Electronic Journal of Combinatorics 26(3), Research paper P3.64, 32 pages, 2019. [doi] [arXiv:1810.09847]
    [supplemental data]
24. Two Disjoint 5-Holes in Point Sets
    Manfred Scheucher.
    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] [pdf]
    In Computational Geometry: Theory and Applications 91, 2020. [doi] [arXiv:1807.10848]
    [supplemental data]
25. On L-shaped Point Set Embeddings of Trees: First Non-embeddable Examples
    with Torsten Mütze.
    In Proceedings of 26th International Symposium on Graph Drawing and Network Visualization (GD 2018), pages 354--360, LNCS 11282, Springer, 2018. [doi]
    In Journal of Graph Algorithms and Applications 24(3), pages 343--369, 2020. [doi] [arXiv:1807.11043]
    [supplemental data]
26. Arrangements of Pseudocircles: On Circularizability
    with Stefan Felsner.
    In Proceedings of 26th International Symposium on Graph Drawing and Network Visualization (GD 2018), pages 555--568, LNCS 11282, Springer, 2018. [doi]
    In Discrete & Computational Geometry 64(3), pages 776--813, 2020. Ricky Pollack Memorial Issue. [doi] [arXiv:1712.02149]
    [supplemental data]
27. Minimal Geometric Graph Representations of Order Types
    with Oswin Aichholzer, Martin Balko, Michael Hoffmann, Jan Kynčl, Wolfgang Mulzer, Irene Parada, Alexander Pilz, Pavel Valtr, Birgit Vogtenhuber, and Emo Welzl.
    In Proceedings of 27th International Symposium on Graph Drawing and Network Visualization (GD 2019), pages 101--113, LNCS 11904, Springer, 2019. [doi]
    In Journal of Graph Algorithms and Applications 24(4), pages 551--572, 2020. Special issue on selected papers from GD 2019. [doi] [arXiv:1908.05124]
28. Almost-equidistant sets
    with Martin Balko, Attila Pór, Konrad Swanepoel, and Pavel Valtr.
    In Graphs and Combinatorics 36, pages 729--754, 2020. [doi] [arXiv:1706.06375]
    [supplemental data]
29. Arrangements of Pseudocircles: Triangles and Drawings
    with Stefan Felsner.
    In Proceedings of 25th International Symposium on Graph Drawing and Network Visualization (GD 2017), pages 127--139, LNCS 10692, Springer, 2017. [pdf] [doi]
    In Discrete & Computational Geometry 65, pages 261--278, 2021. [doi] [arXiv:1708.06449]
    [supplemental data]
30. A superlinear lower bound on the number of 5-holes
    with Oswin Aichholzer, Martin Balko, Thomas Hackl, Jan Kynčl, Irene Parada, Pavel Valtr, and Birgit Vogtenhuber.
    In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG 2017), pages 8:1--8:16, LIPIcs 77, Schloss Dagstuhl, 2017. [pdf] [doi]
    In Journal of Combinatorial Theory, Series A, 173:105236, 2020. [doi] [arXiv:1703.05253]
    [supplemental data]
31. Strongly Monotone Drawings of Planar Graphs
    with Stefan Felsner, Alexander Igamberdiev, Philipp Kindermann, Boris Klemz, and Tamara Mchedlidze.
    In Proceedings of the 32nd International Symposium on Computational Geometry (SoCG 2016), pages 37:1--37:15, LIPIcs 51, Schloss Dagstuhl, 2016. [pdf] [doi] [arXiv:1601.01598]
32. Planar L-Shaped Point Set Embeddings of Trees (this work is based on my Master's thesis)
    with Oswin Aichholzer and Thomas Hackl.
    In Proceedings of the 32nd European Workshop on Computational Geometry (EuroCG), 2016. [url] [pdf]

Theses

• Points, Lines, and Circles: Some Contributions to Combinatorial Geometry
  PhD thesis, Institut für Mathematik, Technische Universität Berlin, Germany, 2020.
  Supervisor: Stefan Felsner.
  [pdf] [doi]
• Orthogeodesic Point Set Embeddings of Outerplanar Graphs
  Master's thesis, Institute for Software Technology, Graz University of Technology, Austria, 2015.
  Supervisors: Oswin Aichholzer and Thomas Hackl.
  [pdf] [url]
• On Order Types, Projective Classes, and Realizations
  Bachelor's thesis, Institute for Software Technology, Graz University of Technology, Austria, 2014.
  Supervisors: Oswin Aichholzer and Thomas Hackl.
  [pdf]
• Counting Convex 5-Holes
  Bachelor's thesis, Institute for Software Technology, Graz University of Technology, Austria, 2013.
  Supervisors: Oswin Aichholzer and Thomas Hackl.
  [pdf]

Coauthors