DiGeo: Fundamental questions of discrete geometry

Journal papers

  • 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

  • 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]
  • 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]
  • 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)
  • Three Edge-disjoint Plane Spanning Paths in a Point Set (Philipp Kindermann, Jan Kratochvíl, Giuseppe Liotta, Pavel Valtr).
    • In the proceedings of the International Symposium on Graph Drawing and Network Visualization (GD 2023), 2023. [DOI]
    • arXiv:2306.07237 (2023)
  • 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]
  • 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)

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).
  • Extending simple monotone drawings (Jan Kynčl and Jan Soukup).
    • submitted, 2023
    • arXiv:2312.17675 (2023)
    • Extended abstract in the (informal) proceedings of the 40th European Workshop on Computational Geometry (EuroCG 2024), 2024. [Extended abstract]
  • Faces in rectilinear drawings of complete graphs (Martin Balko, Anna Brötzner, Fabian Klute, and Josef Tkadlec).
    • submitted, 2024
    • Extended abstract in the (informal) proceedings of the 40th European Workshop on Computational Geometry (EuroCG 2024), 2024. [Extended abstract]
  • The Erdős-Szekeres Conjecture revisited (Jineon Baek and Martin Balko).
    • submitted, 2024
  • 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]
  • Crossing and non-crossing families (Todor Antić, Birgit Vogtenhuber and Martin Balko).
    • submitted, 2024
  • A survey on ordered Ramsey numbers (Martin Balko).
    • submitted, 2024
  • On forbidden configurations in point-line incidence graphs (Martin Balko and Norá Frankl).
    • 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
  • 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.