DiGeo: Fundamental questions of discrete geometry

Journal papers

  • Extending simple monotone drawings (Jan Kynčl and Jan Soukup).
    • In The Electronic Journal of Combinatorics, 2026. [DOI]
    • 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]
  • Computing Largest Minimum Color-Spanning Intervals of Imprecise Points (Ankush Acharyya, Vahideh Keikha, Maria Saumell, and Rodrigo I. Silveira).
    • In Theory of Computing Systems, 2026. [DOI]
    • In the proceedings of the 16th Latin American Symposium on Theoretical Informatics (LATIN 2024), 2024. [DOI]
  • On the Hardness of Switching to a Small Number of Edges (Vít Jelínek, Eva Jelínková and Jan Kratochvíl).
    • In Journal of Graph Theory, 2026. [DOI]
  • Constrained Outer-String Representations (Therese Biedl, Sabine Cornelsen, Jan Kratochvíl and Ignaz Rutter).
    • In Discrete Applied Mathematics, 2026. [DOI]
    • In the proceedings of the International Symposium on Graph Drawing and Network Visualization (GD 2024), 2024. [DOI]
  • Estimating multicolor ordered Ramsey numbers (Martin Balko and Klára Grinerová).
    • In Discrete Mathematics, 2026. [ DOI]
    • 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 Journal of Combinatorial Theory, Series A, 2026. [ DOI]
    • In the proceedings of Symposium on Computational Geometry (SoCG 2025), 2025. [DOI]
  • A survey on ordered Ramsey numbers (Martin Balko).
    • In Bolyai Society Mathematical Studies, 2026. [DOI]
    • 2502.02155 (2025)
  • 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 Graphs and Combinatorics, 2025. [DOI]
    • Extended abstract the proceedings of the International Symposium on Graph Drawing and Network Visualization (GD 2024), 2024. [DOI]
    • arXiv:2410.05580 (2024)
  • On forbidden configurations in point-line incidence graphs (Martin Balko and Nóra Frankl).
    • In SIAM Journal on Discrete MAthematics (SIDMA), 2025. [DOI]
  • 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]
  • Connected Matchings (Oswin Aichholzer, Sergio Cabello, Viola Mészáros, and Patrick Schnider, Jan Soukup).
    • In Computational Geometry (CGTA), 2025. [DOI]
    • arXiv:2407.06131
    • 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 [DOI]
    • 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

  • High Beer Index implies big hollow triangles (Arun Kumar Das, Vít Jelínek, Jan Kinčl, Martin Pergel, Felix Schröder, Peter Stumpf and Pavel Valtr)
      In the proceedings of the 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026), 2026. [DOI]
  • How Close is a Tree to a Euclidean Minimum Spanning Tree? (Todor Antić, Jiři Fiala, Jelena Glišić, Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Jan Kratochvíl, Giuseppe Liotta, Morteza Saghafian, Maria Saumell, Krisztina Szilágyi and Pavel Valtr).
    • To appear in the proceedings of the International Symposium on Graph Drawing and Network Visualization (GD 2026), 2026.
    • arXiv:2607.20007
  • Two Results on Outer-String Graphs (Todor Antić, Vít Jelínek, Jan Kratochvíl and Peter Stumpf).
    • To appear in the proceedings of the International Symposium on Graph Drawing and Network Visualization (GD 2026), 2026.
    • arXiv:2605.12253
  • On Reconstructing a Convex Polygon from Partial Information (Alexander Baumann, Therese Biedl, Mahmoud Elashmawi, Simon D. Fink, Maria Saumell, André Schulz)
    • To appear in the proceeding of the 38th Canadian Conference on Computational Geometry (CCCG 2026), 2026.
  • Complexity of Perfect (1, 2)-Dominating Sets in Low-Degree Graphs (Urszula Bednarz, Jan Kratochvíl and Adrian Michalski).
    • In the proceedings of the 20th International Conference and Workshop on Alogrithms and Computation (WALCOM 2026), 2026. [DOI]
  • The Gate-Cover Problem (Esther M. Arkin, Alon Efrat, Omrit Filtser, Stephen G. Kobourov and Jan Kratochvíl).
    • In the proceedings of the 20th International Conference and Workshop on Alogrithms and Computation (WALCOM 2026), 2026. [DOI]
  • How many times can two minimum spanning trees cross? (Todor Antić, Morteza Saghafian, Maria Saumell, Felix Schröder, Josef Tkadlec and Pavel Valtr).
    • To appear in the proceedings of the 17th Latin Ameerican Theoretical Informatics Symposium (LATIN 2026), 2026.
    • arXiv:2601.20060
  • Edge-Constrained Hamiltonian Paths in a Poit Set (Todor Antić, Aleksa Džuklevski, Jiří Fiala, Jan Kratochvíl, Giuseppe Liotta, Morteza Saghafian, Maria Saumell and Johannes Zink).
    • In the proceedings of the 51st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2026), 2026. [DOI]
    • arXiv:2511.22526
  • Unbent collections of orthogonal drawings (Todor Antić, Giuseppe Liotta, Tomáš Masařík, Giacomo Ortali, Matthias Pfretzschner, Peter Stumpf, Alexander Wolff and Johannes Zink).
    • In the proceedings of the 51st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2025), 2025. [DOI]
  • 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 Schröder, 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]
  • 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]
  • 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]
  • 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)
  • 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 Schröder 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 Schröder).
    • In the proceedings of the International Symposium on Graph Drawing and Network Visualization (GD 2024), 2024. [DOI]
    • arXiv:2409.01723 (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

  • Thrackles on nonplanar surfaces (César Hernández-Vélez, Jan Kynčl and Gelasio Salazar)
  • k-arrangements of pseudolines and pseudocircles (Jan Kynčl, Carolina Medina and Gelasio Salazar)
  • A General Upper Bound on Multicolor Ordered Ramsey Numbers (Martin Balko and Klára Grinerová).
  • On edge-ordered Ramsey numbers of hypergraphs (Martin Balko and Jelena Glišić).
  • Proof of the Harary--Hil conjecture: an exposition (Martin Balko).
  • 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).
  • 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 Schröder).

Informal proceedings


Awards

  • Klára Grinerová won the 1st prize at the student competition SVOČ 2026 for her paper A general upper bound on multicolor ordered Ramsey numbers
  • Eliška Červenková receiveed the prize of Jirka Matoušek for her paper Construction of 1-planar unit distance graphs with more edges than matchstick graphs
  • 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
  • Klára 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
  • Todor Antić won the best thesis award for his master thesis Relationships between k-planar and h-quasiplanar 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

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