1. Long alternating paths in bicolored point sets (with J. Pach and G. Toth), Discrete Mathematics 308 (2008), Issue 19, 4315-4321. doi:10.1016/j.disc.2007.08.013
   • preliminary version in: Proceedings of the 12th International Symposium on Graph Drawing (GD 2004), Lecture Notes in Computer Science 3383, 340-348, Springer, Berlin, 2005. doi:10.1007/978-3-540-31843-9_34
2. Probabilistic strategies for the partition and plurality problems (with Z. Dvorak, V. Jelinek, D. Kral and M. Saks), Random Structures Algorithms 30 (2007), no. 1-2, 63-77. doi:10.1002/rsa.20148
   • extended abstract: Three optimal algorithms for balls of three colors (with Z. Dvorak, V. Jelinek, D. Kral and M. Saks), in: Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS 2005), Lecture Notes in Computer Science 3404, 206-217, Springer, Berlin, 2005. doi:10.1007/978-3-540-31856-9_17
3. On edges crossing few other edges in simple topological complete graphs (with P. Valtr), Discrete Mathematics 309 (2009), Issue 7, 1917-1923. doi:10.1016/j.disc.2008.03.005
   • preliminary version in: Proceedings of the 13th International Symposium on Graph Drawing (GD 2005), Lecture Notes in Computer Science 3843, 274-284, Springer, Berlin, 2006. doi:10.1007/11618058_25
4. Monochromatic triangles in two-colored plane (with V. Jelinek, R. Stolar and T. Valla), Combinatorica 29 (2009), Issue 6, 699-718. doi:10.1007/s00493-009-2291-y, readcube link
   • presentation
   • preliminary version: arXiv:math/0701940
5. The maximum piercing number for some classes of convex sets with (4, 3)-property (with M. Tancer), The Electronic Journal of Combinatorics 15 (2008), R27, 16 pp. doi:10.37236/751
6. Improvement on the decay of crossing numbers (with J. Cerny and G. Toth), Graphs and Combinatorics 29 (2013), Issue 3, 365-371. doi:10.1007/s00373-012-1137-3, readcube link
   • preliminary version: arXiv:1201.5421
   • extended abstract in: Proceedings of the 15th International Symposium on Graph Drawing (GD 2007), Lecture Notes in Computer Science 4875, 25-30, Springer, Berlin, 2008. doi:10.1007/978-3-540-77537-9_5
7. Enumeration of simple complete topological graphs, European Journal of Combinatorics 30 (2009), Issue 7, 1676-1685. doi:10.1016/j.ejc.2009.03.005, correction
   • presentation
   • extended abstract in: Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (Euro Comb 07), Electronic Notes in Discrete Mathematics 29 (2007), 295-299. doi:10.1016/j.endm.2007.07.051
8. Simple realizability of complete abstract topological graphs in P, Discrete and Computational Geometry 45 (2011), Issue 3, 383-399. doi:10.1007/s00454-010-9320-x, readcube link
   • presentation
   • preliminary version: The complexity of several realizability problems for abstract topological graphs, in: Proceedings of the 15th International Symposium on Graph Drawing (GD 2007), Lecture Notes in Computer Science 4875, 137-158, Springer, Berlin, 2008. doi:10.1007/978-3-540-77537-9_16
9. Ramsey-type constructions for arrangements of segments, European Journal of Combinatorics 33 (2012), Issue 3, 336-339. doi:10.1016/j.ejc.2011.09.006
   • presentation
   • extended abstract in: Proceedings of The International Conference on Topological and Geometric Graph Theory (TGGT), Electronic Notes in Discrete Mathematics 31 (2008), 265-269. doi:10.1016/j.endm.2008.06.054
   • extended version including constructions of non-flattenable arrangements: arXiv:1010.2167
10. 6-critical graphs on the Klein bottle (with K. Kawarabayashi, D. Kral and B. Lidicky), SIAM Journal on Discrete Mathematics 23 (2009), Issue 1, 372-383. doi:10.1137/070706835
    • extended abstract: Six-critical graphs on the Klein bottle (with N. Chenette, K. Kawarabayashi, D. Kral, B. Lidicky, L. Postle, N. Streib, R. Thomas and C. Yerger), in: Proceedings of The International Conference on Topological and Geometric Graph Theory (TGGT), Electronic Notes in Discrete Mathematics 31 (2008), 235-240. doi:10.1016/j.endm.2008.06.047
11. Logspace reduction of directed reachability for bounded genus graphs to the planar case (with T. Vyskocil), ACM Transactions on Computation Theory 1 (2010), Issue 3, 1-11. doi:10.1145/1714450.1714451
    • presentation in Czech
    • preliminary version: ECCC Report TR09-050
12. Irreversible 2-conversion set in graphs of bounded degree (with B. Lidicky and T. Vyskocil), Discrete Mathematics & Theoretical Computer Science 19 (2017), no. 3, Paper No. 5, 18pp. link
    • arxiv versions: arXiv:1412.4188
    • early version: Irreversible 2-conversion set is NP-complete, KAM-DIMATIA Series 2009-933
13. Universal sets for straight-line embeddings of bicolored graphs (with J. Cibulka, V. Meszaros, R. Stolar and P. Valtr), in: J. Pach (Ed.), Thirty Essays on Geometric Graph Theory, 101-119, Springer, 2013, ISBN 978-1-4614-0109-4. doi:10.1007/978-1-4614-0110-0_8
    • preliminary version: arXiv:1102.0874
    • earlier conference version: Hamiltonian alternating paths on bicolored double-chains (with J. Cibulka, V. Meszaros, R. Stolar and P. Valtr), in: Proceedings of the 16th International Symposium on Graph Drawing (GD 2008), Lecture Notes in Computer Science 5417, 181-192, Springer, Berlin, 2009. doi:10.1007/978-3-642-00219-9_18
14. On three measures of non-convexity (with J. Cibulka, M. Korbelar, V. Meszaros, R. Stolar and P. Valtr), Israel Journal of Mathematics 218 (2017), Issue 1, 331-369. doi:10.1007/s11856-017-1467-1, readcube link
    • presentation in Czech
    • preliminary version: arXiv:1410.0407
    • extended abstract: On three parameters of invisibility graphs (with J. Cibulka, V. Meszaros, R. Stolar and P. Valtr), in: Computing and Combinatorics, proceedings of the 16th Annual International Computing and Combinatorics Conference (COCOON 2010), Lecture Notes in Computer Science 6196, 192-198, Springer, Berlin, 2010. doi:10.1007/978-3-642-14031-0_22
    • extended abstract also in: (informal) proceedings of the XV Spanish Meeting on Computational Geometry, 2013. link
15. Solution of Peter Winkler's pizza problem (with J. Cibulka, V. Meszaros, R. Stolar and P. Valtr), in: G. Katona, A. Schrijver, T. Szonyi (Eds.), Fete of Combinatorics and Computer Science, Bolyai Society Mathematical Studies 20, 63-93, Springer, 2010, ISBN 978-3-642-13579-8. doi:10.1007/978-3-642-13580-4_4
    • preliminary version: arXiv:0812.4322
    • extended abstract in: Combinatorial Algorithms, proceedings of the 20th International Workshop on Combinatorial Algorithms (IWOCA 2009), Lecture Notes in Computer Science 5874, 356-367, Springer, Berlin, 2009. doi:10.1007/978-3-642-10217-2_35
16. Graph sharing games: complexity and connectivity (with J. Cibulka, V. Meszaros, R. Stolar and P. Valtr), Theoretical Computer Science 494 (2013), 49-62. doi:10.1016/j.tcs.2012.12.029
    • preliminary version: arXiv:1202.0847
    • extended abstract in: Proceedings of the 7th Annual Conference on Theory and Applications of Models of Computation (TAMC 2010), Lecture Notes in Computer Science 6108, 340-349, Springer, Berlin, 2010. doi:10.1007/978-3-642-13562-0_31
17. Tight bounds on the maximum size of a set of permutations with bounded VC-dimension (with J. Cibulka), Journal of Combinatorial Theory, Series A 119 (2012), Issue 7, 1461-1478. doi:10.1016/j.jcta.2012.04.004
    • presentation: see Josef's webpage
    • preliminary version: arXiv:1104.5007
    • extended abstract in: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), 1113-1122. doi:10.1137/1.9781611973099.87
18. Improved enumeration of simple topological graphs, Discrete and Computational Geometry 50 (2013), Issue 3, 727-770. doi:10.1007/s00454-013-9535-8, readcube link, corrections
    • presentation
    • corrected version: arXiv:1212.2950
    • extended abstract in: (informal) proceedings of the XV Spanish Meeting on Computational Geometry, 2013. link
19. On planar point sets with the pentagon property (with J. Cibulka and P. Valtr), in preparation.
    • presentation: see Josef's webpage
    • extended abstract in: Proceedings of the 29th ACM Symposium on Computational Geometry (SoCG 2013), 81-90, ACM New York, NY, 2013. doi:10.1145/2462356.2462406
20. On the nonexistence of k-reptile simplices in R^3 and R^4 (with Z. Patakova), The Electronic Journal of Combinatorics 24 (2017), Issue 3, P3.1, 44 pp. doi:10.37236/6113
    • preliminary version: arXiv:1602.04668
    • extended abstract in: The Seventh European Conference on Combinatorics, Graph Theory and Applications, CRM Series 16 (2013), 191-196, Scuola Normale Superiore. doi:10.1007/978-88-7642-475-5_31,
    • extended abstract also in: (informal) proceedings of the XV Spanish Meeting on Computational Geometry, 2013. link
21. Crossing numbers and combinatorial characterization of monotone drawings of K_n (with M. Balko and R. Fulek), Discrete and Computational Geometry 53 (2015), Issue 1, 107-143. doi:10.1007/s00454-014-9644-z, readcube link
    • presentation
    • preliminary version: arXiv:1312.3679
    • extended abstract: Monotone crossing number of complete graphs (with M. Balko and R. Fulek), in: (informal) proceedings of the XV Spanish Meeting on Computational Geometry, 2013. link
22. Saturated simple and k-simple topological graphs (with J. Pach, R. Radoicic and G. Toth), Computational Geometry: Theory and Applications 48 (2015), Issue 4, 295-310. doi:10.1016/j.comgeo.2014.10.008
    • preliminary version: arXiv:1309.1046
23. Peeling potatoes near-optimally in near-linear time (with S. Cabello, J. Cibulka, M. Saumell and P. Valtr), SIAM Journal on Computing 46 (2017), no. 5, 1574-1602. doi:10.1137/16M1079695
    • preliminary version: arXiv:1406.1368
    • extended abstract in: Proceedings of the 30th ACM Symposium on Computational Geometry (SoCG 2014), 224-231, ACM New York, NY, 2014. doi:10.1145/2582112.2582159
24. Bounds for Pach's selection theorem and for the minimum solid angle in a simplex (with R. Karasev, P. Patak, Z. Patakova and M. Tancer), Discrete and Computational Geometry 54 (2015), Issue 3, 610-636. doi:10.1007/s00454-015-9720-z, readcube link
    • preliminary version: arXiv:1403.8147
25. Clustered planarity testing revisited (with R. Fulek, I. Malinovic and D. Palvolgyi), The Electronic Journal of Combinatorics 22 (2015), Issue 4, P4.24, 29 pp. doi:10.37236/5002
    • presentation
    • preliminary version: arXiv:1305.4519
    • extended abstract in: Proceedings of the 22nd International Symposium on Graph Drawing (GD 2014), Lecture Notes in Computer Science 8871, 428-439, Springer, Berlin, 2014. doi:10.1007/978-3-662-45803-7_36
26. The hamburger theorem (with M. Kano), Computational Geometry: Theory and Applications 68 (2018), 167-173. doi:10.1016/j.comgeo.2017.06.012
    • presentation
    • corrected version: arXiv:1503.06856
    • extended abstract in: (informal) proceedings of the XVI Spanish Meeting on Computational Geometry, 2015. link
27. Ramsey numbers of ordered graphs (with M. Balko, J. Cibulka and K. Kral), The Electronic Journal of Combinatorics 27 (2020), Issue 1, P1.16, 32 pp. doi:10.37236/7816
    • preliminary version: arXiv:1310.7208
    • extended abstract in: Proceedings of The Eight European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015), Electronic Notes in Discrete Mathematics 49 (2015), 419-424. doi:10.1016/j.endm.2015.06.059
28. Simple realizability of complete abstract topological graphs simplified, Discrete and Computational Geometry 64 (2020), Issue 1, 1-27. doi:10.1007/s00454-020-00204-0, readcube link
    • presentation
    • preliminary version: arXiv:1608.05867
    • extended abstract in: Proceedings of the 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015), Lecture Notes in Computer Science 9411, 309-320, Springer, 2015. doi:10.1007/978-3-319-27261-0_26
    • extended abstract in: (informal) proceedings of the XVI Spanish Meeting on Computational Geometry, 2015. link
29. Better upper bounds on the Füredi–Hajnal limits of permutations (with J. Cibulka), submitted.
    • presentation: see Josef's webpage
    • preliminary version: arXiv:1607.07491
    • extended abstract in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), 2280-2293. doi:10.1137/1.9781611974782.150
30. Hardness of permutation pattern matching (with V. Jelinek), manuscript.
    • preliminary version: arXiv:1608.00529
    • extended abstract in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), 378-396. doi:10.1137/1.9781611974782.24
31. Near equipartitions of colored point sets (with A. F. Holmsen and C. Valculescu), Computational Geometry: Theory and Applications 65 (2017), 35-42. doi:10.1016/j.comgeo.2017.05.001
    • presentation in Czech
    • preliminary version: arXiv:1602.02264
32. Unified Hanani–Tutte theorem (with R. Fulek and D. Palvolgyi), The Electronic Journal of Combinatorics 24 (2017), Issue 3, P3.18, 8 pp. doi:10.37236/6663
    • preliminary version: arXiv:1612.00688
33. A superlinear lower bound on the number of 5-holes (with O. Aichholzer, M. Balko, T. Hackl, I. Parada, M. Scheucher, P. Valtr and B. Vogtenhuber), Journal of Combinatorial Theory, Series A 173 (2020), 105236. doi:10.1016/j.jcta.2020.105236
    • preliminary version: arXiv:1703.05253
    • extended abstract in: Proceedings of the 33rd International Symposium on Computational Geometry (SoCG 2017), Leibniz International Proceedings in Informatics (LIPIcs) 77, 8:1-8:16, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. doi:10.4230/LIPIcs.SoCG.2017.8
34. Induced Ramsey-type results and binary predicates for point sets (with M. Balko, S. Langerman and A. Pilz), The Electronic Journal of Combinatorics 24 (2017), Issue 4, P4.24, 22 pp. doi:10.37236/7039
    • preliminary version: arXiv:1705.01909
    • extended abstract in: Proceedings of The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'17), Electronic Notes in Discrete Mathematics 61 (2017), 77-83. doi:10.1016/j.endm.2017.06.023
35. Counterexample to an extension of the Hanani–Tutte theorem on the surface of genus 4 (with R. Fulek), Combinatorica 39 (2019), Issue 6, 1267-1279. doi:10.1007/s00493-019-3905-7
    • presentation
    • preliminary version: arXiv:1709.00508
36. Hanani–Tutte for approximating maps of graphs (with R. Fulek), manuscript.
    • preliminary version: arXiv:1705.05243
    • extended abstract in: Proceedings of the 34th International Symposium on Computational Geometry (SoCG 2018), Leibniz International Proceedings in Informatics (LIPIcs) 99, 39:1-39:15, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. doi:10.4230/LIPIcs.SoCG.2018.39
37. The Z2-genus of Kuratowski minors (with R. Fulek), Discrete and Computational Geometry 68 (2022), Issue 2, 425-447. doi:10.1007/s00454-022-00412-w, readcube link
    • presentation
    • preliminary version: arXiv:1803.05085
    • extended abstract in: Proceedings of the 34th International Symposium on Computational Geometry (SoCG 2018), Leibniz International Proceedings in Informatics (LIPIcs) 99, 40:1-40:14, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. doi:10.4230/LIPIcs.SoCG.2018.40
38. On the growth of the Möbius function of permutations (with V. Jelinek, I. Kantor and M. Tancer), Journal of Combinatorial Theory, Series A 169 (2020), 105121. doi:10.1016/j.jcta.2019.105121
    • preliminary version: arXiv:1809.05774
39. Zeros of the Möbius function of permutations (with R. Brignall, V. Jelinek and D. Marchant), Mathematika 65 (2019), no. 4, 1074-1092. doi:10.1112/S0025579319000251
    • preliminary version: arXiv:1810.05449
40. Z2-genus of graphs and minimum rank of partial symmetric matrices (with R. Fulek), manuscript.
    • preliminary version: arXiv:1903.08637
    • extended abstract in: Proceedings of the 35th International Symposium on Computational Geometry (SoCG 2019), Leibniz International Proceedings in Informatics (LIPIcs) 129, 39:1-39:16, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019. doi:10.4230/LIPIcs.SoCG.2019.39
41. Minimal representations of order types by geometric graphs (with O. Aichholzer, M. Balko, M. Hoffmann, W. Mulzer, I. Parada, A. Pilz, M. Scheucher, P. Valtr, B. Vogtenhuber and E. Welzl), Journal of Graph Algorithms and Applications 24 (2020), no. 4, 551-572. doi:10.7155/jgaa.00545
    • preliminary version: arXiv:1908.05124
    • extended abstract in: Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019), Lecture Notes in Computer Science 11904, 101-113, Springer, 2019. doi:110.1007/978-3-030-35802-0_8
42. On crossing-families in planar point sets (with O. Aichholzer, M. Scheucher, P. Valtr and B. Vogtenhuber), Computational Geometry: Theory and Applications 107 (2022), Paper No. 101899, 8 pp. doi:10.1016/j.comgeo.2022.101899
    • preliminary version: arXiv:2109.10705
    • extended abstract: On 4-crossing-families in point sets and an asymptotic upper bound (with O. Aichholzer, M. Scheucher, and B. Vogtenhuber), in: (informal) proceedings of the 37th European Workshop on Computational Geometry (EuroCG 2021), 2021. link
43. On the maximum number of crossings in star-simple drawings of K_n with no empty lens (with S. Felsner, M. Hoffmann, K. Knorr and I. Parada), Journal of Graph Algorithms and Applications 26 (2022), no. 3, 381-399. doi:10.7155/jgaa.00600
44. Spiraling and folding: the topological view (with M. Schaefer, E. Sedgwick and D. Stefankovic), Discrete and Computational Geometry 72 (2024), no. 1, 246-268. doi:10.1007/s00454-023-00603-z
    • preliminary version: arXiv:2206.07849
45. Drawings of complete multipartite graphs up to triangle flips (with O. Aichholzer, M.-K. Chiu, H. P. Hoang, M. Hoffmann, Y. Maus, B. Vogtenhuber and A. Weinberger), submitted.
    • preliminary version: arXiv:2303.07401
    • extended abstract in: Proceedings of the 39th International Symposium on Computational Geometry (SoCG 2023), Leibniz International Proceedings in Informatics (LIPIcs) 258, 6:1--6:16, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2023. doi:10.4230/LIPIcs.SoCG.2023.6
46. Extending simple monotone drawings (with J. Soukup), submitted.
    • preliminary version: arXiv:2312.17675

ORCID®: https://orcid.org/0000-0003-4908-4703

Papers and manuscripts available at arXiv.org: http://arxiv.org/a/kyncl_j_1.html

Theses:

• Crossings in topological graphs, master thesis, 2006; advisor: Doc. RNDr. Pavel Valtr, Dr. presentation

• Combinatorial problems in geometry, doctoral thesis, 2013; advisor: Doc. RNDr. Pavel Valtr, Dr. presentation