DiGeo: Fundamental questions of discrete geometry

Journal papers

  • On forbidden configurations in point-line incidence graphs (Martin Balko and Norá Frankl).
    • To appear in SIAM Journal on Discrete MAthematics (SIDMA), 2026.
  • Faces in rectilinear drawings of complete graphs (Martin Balko, Anna Brötzner, Fabian Klute, and Josef Tkadlec).
    • In the European Journal of Combinatorics, 2025. [DOI]
    • Extended abstract in the (informal) proceedings of the 40th European Workshop on Computational Geometry (EuroCG 2024), 2024. [Extended abstract]
  • Three Edge-disjoint Plane Spanning Paths in a Point Set (Philipp Kindermann, Jan Kratochvíl, Giuseppe Liotta, Pavel Valtr).
    • In Discrete Mathematics 349(3), 2026
    • In the proceedings of the International Symposium on Graph Drawing and Network Visualization (GD 2023), 2023. [DOI]
    • arXiv:2306.07237 (2023)
  • Inversion Sequences Avoiding a Triple of Patterns of 3 Letters (David Callan, Vít Jelínek, and Toufik Mansour).
    • In the Electronic Journal of Combinatorics (E-JC), 2023. [DOI]
  • On ordered Ramsey numbers of matchings versus triangles (Martin Balko, Marian Poljak).
    • In the Electronic Journal of Combinatorics (E-JC), 2024. [DOI]
    • In the proceedings of the European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2023), 2023. [DOI]

Conference contributions

  • Edge-Constrained Hamiltonian Paths in a Point Set (Todor Antić, Aleksa Džuklevski, Jiří Fiala, Jan Kratochvíl, Giuseppe Liotta, Morteza Saghafian, Maria Saumell and Johannes Zink).
    • To appear in the proceedings of the 51st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2026), 2026.
  • Unbent collections of orthogonal drawings (Todor Antić, Giuseppe Liotta, Tomáš Masařík, Giacomo Ortali, Matthias Pfretzschner, Peter Stumpf, Alexander Wolff and Johannes Zink).
    • To appear in the proceedings of the 51st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2025), 2025.
  • 1-planar unit distance graphs with more edges than matchstick graphs (Eliška Červenková and Jan Kratochvíl).
    • In the proceedings of the International Symposium on Graph Drawing and Network Visualization (GD 2025), 2025. [DOI]
  • Bend Number of Cocomparability Graphs (Todor Antić, Vít Jelínek, Maritn Pergel, Felix Schroder, Peter Stumpf and Pavel Valtr).
    • In the proceedings of the International Symposium on Graph Drawing and Network Visualization (GD 2025), 2025. [DOI]
  • Crossing and non-crossing families (Todor Antić, Martin Balko and Birgit Vogtenhuber).
    • In the proceedings of the International Symposium on Graph Drawing and Network Visualization (GD 2025), 2025. [DOI]
  • Estimating multicolor ordered Ramsey numbers (Martin Balko and Klára Grínerová).
    • In the proceedings of the European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2025) 81-87, 2025. [LINK]
  • The Erdős-Szekeres Conjecture revisited (Jineon Baek and Martin Balko).
    • In the proceedings of Symposium on Computational Geometry (SoCG 2025), 2025. [DOI]
  • Guarding a 1.5D terrain with Imprecise Viewpoints (Vahideh Keikha, Maarten Loffler, Maria Saumell, and Pavel Valtr).
    • In proceedings of the 36th International Workshop on Combinatorial Algorithms (IWOCA 2025), 2025. [DOI]
    • Extended abstract in the (informal) proceedings of the 41st European Workshop on Computational Geometry (EuroCG 2025), 2025. [Extended abstract]
  • Extending simple monotone drawings (Jan Kynčl and Jan Soukup).
    • In proceedings of the 36th International Workshop on Combinatorial Algorithms (IWOCA 2025), 2025. [DOI]
    • arXiv:2312.17675 (2023)
    • Extended abstract in the (informal) proceedings of the 40th European Workshop on Computational Geometry (EuroCG 2024), 2024. [Extended abstract]
  • Simultaneous Contact Representations of Planar Graphs (Jan Kratochvíl and Melanie Reihl).
    • In the proceedings of International Symposium on Fundamentals of Computation Theory (FCT 2025), 2025. [DOI]
  • Computing Largest Minimum Color-Spanning Intervals of Imprecise Points (Ankush Acharyya, Vahideh Keikha, Maria Saumell, and Rodrigo I. Silveira).
    • In the proceedings of the 16th Latin American Symposium on Theoretical Informatics (LATIN 2024), 2024. [DOI]
  • On the Uncrossed Numbers of Graphs (Martin Balko, Petr Hliněný, Tomáš Masařík, Joachim Orthaber, Birgit Vogtenhuber and Mirko H. Wagner).
    • In the proceedings of the International Symposium on Graph Drawing and Network Visualization (GD 2024), 2024. [DOI]
    • arXiv:2407.21206 (2024)
  • Constrained Outer-String Representations (Therese Biedl, Sabine Cornelsen, Jan Kratochvíl and Ignaz Rutter).
    • In the proceedings of the International Symposium on Graph Drawing and Network Visualization (GD 2024), 2024. [DOI]
  • Convex-geometric k-planar graphs are convex-geometric (k+1)-quasiplanar (Todor Antić).
    • In the proceedings of the 35th International Workshop on Combinatorial Algorithms (IWOCA 2024), 2024. [DOI]
  • Star-Forest Decompositions of Complete Graphs (Todor Antić, Jelena Glišić and Milan Milivojčević).
    • In the proceedings of the 35th International Workshop on Combinatorial Algorithms (IWOCA 2024), 2024. [DOI]
    • arXiv:2402.11044 (2024)
    • Extended abstract in the (informal) proceedings of the 40th European Workshop on Computational Geometry (EuroCG 2024), 2024. [Extended abstract]
  • Grid-edge unfolding orthostacks with rectangular slabs (Klará Pernicová).
    • In the proceedings of 36th Canadian Conference on Computational Geometry (CCCG 2024), 2024. [LINK]
  • The Hierarchy of Hereditary Sorting Operators (Vít Jelínek, Michal Opler, and Jakub Pekárek).
    • In the proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), 2024. [DOI]
  • The Density Formula: One Lemma to Bound Them All (Michael Kaufmann, Boris Klemz, Kristin Knorr, Meghana M. Reddy, Felix Schroder and Torsten Ueckerdt).
    • In the proceedings of the International Symposium on Graph Drawing and Network Visualization (GD 2024), 2024. [DOI]
    • arXiv:2311.06193 (2024)
  • Holes in Convex and Simple Drawings (Helena Bergold, Joachim Orthaber, Manfred Scheucher and Felix Schroder).
    • In the proceedings of the International Symposium on Graph Drawing and Network Visualization (GD 2024), 2024. [DOI]
    • arXiv:2409.01723 (2024)
  • Noncrossing Longest Paths and Cycles (Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, David Eppstein, Anil Maheshwari, Saeed Odak, Michiel Smid, Csaba D. Tóth, and Pavel Valtr).
    • In the proceedings of the International Symposium on Graph Drawing and Network Visualization (GD 2024), 2024. [DOI]
    • arXiv:2410.05580 (2024)
  • Improved Bounds for the Binary Paint Shop Problem (Jaroslav Hančl, Adam Kabela, Michal Opler, Jakub Sosnovec, Robert Šámal, and Pavel Valtr).
    • In the proceedings of the International Computing and Combinatorics Conference (COCOON 2023), 2023. [DOI]
  • String graphs with precise number of intersections (Petr Chmel and Vít Jelínek).
    • In the proceedings of the International Symposium on Graph Drawing and Network Visualization (GD 2023), 2023. [DOI]
  • The Parametrized Complexity of the Segment Number (Sabine Cornelsen, Giordano Da Lozzo, Luca Grilli, Siddharth Gupta, Jan Kratochvíl, Alexander Wolff).
    • In the proceedings of the International Symposium on Graph Drawing and Network Visualization (GD 2023), 2023. [DOI]
    • arXiv:2308.15416 (2023)

Preprints

  • Structure of betweenness uniform graphs with low values of betweenness centrality (Babak Ghanbari, David Hartman, Vít Jelínek, Aneta Pokorná, Robert Šámal, and Pavel Valtr).
  • Connected Matchings (Oswin Aichholzer, Sergio Cabello, Viola Mészáros, and Patrick Schnider, Jan Soukup).
    • submitted, 2024
    • arXiv:2407.06131
    • Extended abstract in the (informal) proceedings of the 40th European Workshop on Computational Geometry (EuroCG 2024), 2024. [Extended abstract]
  • A survey on ordered Ramsey numbers (Martin Balko).
    • submitted, 2024
  • Reconfigurations of Plane Caterpillars and Paths (Todor Antić, Guillermo Gamboa Quintero and Jelena Glišić).
  • Bicolored point sets admitting non-crossing alternating Hamiltonian paths (Jan Soukup).
  • Finding hardness reductions automatically using SAT solvers (Helena Bergold, Manfred Scheucher and Felix Schroder).

Informal proceedings


Awards

  • Maria Saumell, Pavel Valtr and their coauthors received the best paper award at IWOCA 2025 for their paper Guarding a 1.5D terrain with Imprecise Viewpoints
  • Klará Grinerová won the 1st prize at the student competition SVOČ 2025 for her paper Estimating multicolor ordered Ramsey numbers
  • Eliška Červenková won 2nd prize at the student competition SVOČ 2025 for her paper Construction of 1-planar unit distance graphs with more edges than matchstick graphs
  • Felix Schröder and his coauthors received the best paper award GD 2024 for their paper The Density Formula: One Lemma to Bound Them All
  • Peter Stumpf and his coauthors received the best poster award at GD 2024 for their poster Level Planarity Is More Difficult Than We Thought
  • Jan Soukup and Jan Kynčl received the best paper award at WG 2024 for their paper Many views of planar point sets
  • Jan Kratochvíl and Nikola Jedličková received the best paper award at IWOCA 2024 for their paper On the Structure of Hamiltonian Graphs with Small Independence Number

This project is funded by the Czech Science Foundation under the grant agreement no. 23-04949X.