Dr. Manfred Scheucher

Contact

Email:
lastname[at]domain, math.tu-berlin.de = domain

Address:
Technische Universität Berlin
Institut für Mathematik
Sekretariat MA 5-1
Strasse des 17. Juni 136
D-10623 Berlin, Germany

Office:
MA 362

Office:
MA 506

About Me

I'm a postdoctoral researcher in the group of Stefan Felsner at TU Berlin (Arbeitsgruppe Diskrete Mathematik) and principal investigator of the DFG project SCHE 2214/1-1 "Approaching Problems from Combinatorics and Geometry using Computer Assistance". Formerly I was part of the D-A-CH collaborative project "Arrangements and Drawings" supported by the DFG Grant FE 340/12-1. Before I finished my PhD at TU Berlin, I did my Bachelor and Master studies at TU Graz. The focus of my research lies in the interface of theoretical computer science and discrete mathematics, in particular, combinatorial geometry. My primary objective is to tackle fundamental mathematical problems by combining classic proving techniques with automated reasoning tools, in particular, SAT solvers and related techniques. Detailed CV

Publications and Preprints

  1. Finding hardness reductions automatically using SAT solvers
    with Helena Bergold and Felix Schröder.
    Preprint available at [arXiv:2402.06397]
  2. An Improved Lower Bound on the Number of Pseudoline Arrangements
    with Fernando Cortés Kühnast, and Justin Dallant, Stefan Felsner.
    To appear in the Proceedings of the 40th International Symposium on Computational Geometry (SoCG 2024).
  3. Saturation results around the Erdős-Szekeres problem
    with Gábor Damásdi, Zichao Dong, and Ji Zeng.
    To appear in the Proceedings of the 40th International Symposium on Computational Geometry (SoCG 2024).
    Preprint available at [arXiv:2312.01223]
  4. Plane Hamiltonian cycles in convex drawings
    with Helena Bergold, Stefan Felsner, Joachim Orthaber and Meghana M. Reddy.
    To appear in the Proceedings of the 40th International Symposium on Computational Geometry (SoCG 2024).
  5. Happy ending: An empty hexagon in every set of 30 points
    with Marijn J. H. Heule.
    To appear in the 30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2024).
    Preprint available at [arXiv:2403.00737]
  6. Flip Graph Connectivity for Arrangements of Pseudolines and Pseudocircles
    with Yan Alves Radtke, Stefan Felsner, Johannes Obenaus, Sandro Roch and Birgit Vogtenhuber.
    To appear at ACM-SIAM Symposium on Discrete Algorithms (SODA24), 2024.
    Preprint available at [arXiv:2310.19711]
  7. SAT-Based Generation of Planar Graphs
    with Markus Kirchweger and Stefan Szeider.
    In the Proceedings of the 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023), pages 14:1--14:17, LIPIcs 271, Schloss Dagstuhl, 2023. [doi]
    [supplemental]
  8. Roudneff's Conjecture in Dimension $4$
    with Rangel Hernández-Ortiz, Kolja Knauer, and Luis Pedro Montejano.
    In the Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2023), pages 561--567, 2023. [doi]
    [supplemental]
  9. Bichromatic Perfect Matchings with Crossings
    with Oswin Aichholzer, Stefan Felsner, Rosna Paul, and Birgit Vogtenhuber.
    To appear in the proceedings of 31th International Symposium on Graph Drawing and Network Visualization (GD 2023). [url]
    Preprint available at [arXiv:2309.00546]
  10. 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]
  11. 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]
  12. Extendability of Higher Dimensional Signotopes
    with Helena Bergold and Stefan Felsner.
    In Proceedings of the 39th International Symposium on Computational Geometry (SoCG 2023), pages 17:1--17:14, LIPIcs 258, Schloss Dagstuhl, 2023. [doi]
    Preprint available at [arXiv:2303.04079]
    [supplemental data]
  13. Arrangements of Pseudocircles: On Digons and Triangles
    with Stefan Felsner and Sandro Roch.
    In Proceedings of 30th International Symposium on Graph Drawing and Network Visualization (GD 2022), pages 441--455, LNCS 13764, Springer, 2023. [doi]
    Preprint available at [arXiv:2208.12110]
  14. 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]
  15. 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]
  16. 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]
  17. 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, pages 29--51, 2022. [doi] [arXiv:2111.12533]
  18. 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]
    In the European Journal of Combinatorics, special issue of EuroComb 2021, article 103839, 2023. [doi] [arXiv:2205.08181]
  19. 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:101899, 2022. Special Issue EuroCG 2021. [doi] [arXiv:2109.10705]
  20. Many Order Types on Integer Grids of Polynomial Size
    Manfred Scheucher.
    In Computational Geometry: Theory and Applications 109:101924, 2023. Special Issue EuroCG 2021. [doi] [arXiv:2007.15334]
  21. 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]
  22. 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 60, 308--326, 2021. [doi] [arXiv:2003.00909]
  23. 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]
  24. 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]
  25. 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]
  26. 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]
  27. 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:101670, 2020. [doi] [arXiv:1807.10848]
    [supplemental data]
  28. 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]
  29. 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]
  30. 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]
  31. 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]
  32. 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]
  33. 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]
  34. 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]
  35. 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]

(c) Manfred Scheucher, March 08 2024 09:37:52.