List of publications and manuscripts (Pavel Valtr)

Mathematical Reviews (results for ''author = Valtr'')

Papers and manuscripts

  1. Convex independent sets and 7-holes in restricted planar point sets, Discrete and Computational Geometry 7 (1992), 135-152
  2. Sets in $R^d$ with no large empty convex subsets, Discrete Mathematics 108 (1992), 115-124
  3. Generalized Davenport-Schinzel sequences with linear upper bound (with R. Adamec and M. Klazar), Discrete Mathematics 108 (1992), 219-229
  4. A Ramsey-type theorem in the plane (with J. Nesetril), Combinatorics, Probability and Computing 3 (1994), 127-135
  5. Unit squares intersecting all secants of a square, Discrete and Computational Geometry 11 (1994), 235-239
  6. Cutting dense point sets in half (with H. Edelsbrunner and E. Welzl), Proc. Tenth Annual Symp. on Comp. Geom., Stony Brook, ACM Press (1994), 203-210; also Discrete and Computational Geometry 17 (1997), 243-255
  7. Generalized Davenport-Schinzel sequences (with M. Klazar), Combinatorica 14 (1994), 463-476
  8. Probability that $n$ random points are in convex position, Discrete and Computational Geometry 13 (1995), 637-643
  9. On the minimum number of empty polygons in planar point sets, Studia Scientiarum Mathematicarum Hungarica 30 (1995), 155-163
  10. Ramsey-remainder (with P. Erdös and Zs. Tuza), European Journal of Combinatorics 17 (1996), 519-532
  11. Lines, line-point incidences and crossing families in dense sets, DIMACS Technical Report 94-55 or Combinatorica 16 (1996), 269-294
  12. The probability that $n$ random points in a triangle are in convex position (abstract), Combinatorica 16 (1996), 567-573
  13. On Mutually Avoiding Sets, in: R.L. Graham and J. Nesetril (eds.), The Mathematics of Paul Erdös II, Springer, Algorithms and Combinatorics 14 (1997), 324-332
  14. Catalan numbers via random planar point sets, Intuitive Geometry (I. Barany, ed.), Bolyai Society Math. Studies 6 (1997), 441-443
  15. Graph drawings with no $k$ pairwise crossing edges, in: G. DiBattista (ed.), Graph Drawing '97, Rome, September 1997, pp. 205-218
  16. The complexity of the lower envelope of segments with $h$ endpoints (with J. Matousek), Intuitive Geometry (I. Barany, ed.), Bolyai Society Math. Studies 6 (1997), 407-411
  17. Ramsey-type results for geometric graphs, II (with Gy. Karolyi, J. Pach, and G. Toth), DIMACS Technical Report 97-13, Discrete and Computational Geometry 20 (1998), 375-388.
  18. Guarding galleries where no point sees a small area, Israel Journal of Mathematics 104 (1998), 1-16
  19. On the density of subgraphs in a graph with bounded independence number DIMACS Technical Report 97-11 and J. Comb. Th., Ser. B, 73 (1998), 146-158.
  20. Finding the convex hull of a dense set, Proceedings of the 3rd Asian Applied Computing Conference (L. M. Patnaik et al, Editors), Kathmandu 2005, World Scientific Publishing 2007, Advances in Computer Science and Engineering: Reports and Monographs - Vol. 2, pp. 37-44.
  21. A Ramsey property of order types (with J. Nesetril), J. of Comb. Th. (Ser. A) 81 (1998), 88-107.
  22. A positive fraction Erdos-Szekeres theorem (with I. Barany), Discrete and Computational Geometry 19 (1998), 335-342.
  23. On geometric graphs with no $k$ pairwise parallel edges, DIMACS Technical Report 97-07 , Discrete and Computational Geometry 19 (1998), 461-469.
  24. Note on the Erdos-Szekeres theorem (with G. Toth), Discrete and Computational Geometry 19 (1998), 457-459, DIMACS Technical Report 97-31.
  25. Geometric graphs with few disjoint edges (with G. Toth), Discrete Comput. Geom. 22 (1999), 633-642 (also Proc. of Ann. Symp. Comput. Geom. 1998, pp. 181-194).
  26. The largest $k$-ball in a $d$-dimensional box (with H. Everett, I. Stojmenovic, and S. Whitesides), Computational Geometry: Theory and Applications 11 (1998), 59-67
  27. On an extremal problem for colored trees, Europ. J. Comb. 20 (1999), 115-121
  28. On galleries with no bad points, DIMACS Technical Report 96-55, Discrete and Computational Geometry 21 (1999), 193-200.
  29. Generalizations of Davenport-Schinzel sequences (survey paper), Contemporary Trends in Discrete Mathematics (Edited by: J. Nesetril, J. Kratochvil, F.S. Roberts, R.L. Graham), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 49 (1999), 349-389.
  30. Induced monochromatic subconfigurations (with J. Nesetril and J. Solymosi), Contemporary Trends in Discrete Mathematics (Edited by: J. Nesetril, J. Kratochvil, F.S. Roberts, R.L. Graham), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 49 (1999), 219-227
  31. Almost-tiling the plane by ellipses (with K. Kuperberg, W. Kuperberg, and J. Matousek), Discrete and Computational Geometry 22 (1999), 367-375.
  32. On visibility and covering by convex sets (with J. Matousek), Israel Journal of Mathematics 113 (1999), 341-379.
  33. Low-distortion embeddings of trees (with R. Babilon, J. Matousek, and J. Maxova), Graph Drawing 2001, Lecture Notes in Comp. Sci. 2265, Springer 2002, pp. 343-351.
  34. The partitioned version of the Erdos-Szekeres theorem (with A. Por), Discrete and Computational Geometry 28 (2002), 625-637.
  35. A sufficient condition for the existence of large empty convex polygons, Discrete and Computational Geometry 28 (2002), 671-682
  36. One line and n points (with B. Gartner, J. Solymosi, F. Tschirschnitz, and E. Welzl), Random Structures and Algorithms 23 (2003), 453-471.
  37. Davenport-Schinzel trees, Combinatorica 23 (2003), 151-184
  38. Point configurations in $d$-space without large subsets in convex position (with Gy. Karolyi), Discrete and Computational Geometry 30 (2003), 277-286.
  39. A Turan-type extremal theory of convex geometric graphs (with P. Brass and Gy. Karolyi), in: B. Aronov et al. (Eds.), Discrete and Computational Geometry--The Goodman-Pollack Festschrift, Springer, Berlin, 2003, pp. 275-300.
  40. VC-dimension of exterior visibility (with K. Daniilidis, V. Isler, and S. Kannan), IEEE Transactions on Pattern Analysis and Machine Intelligence 26 (2004), 667-671.
  41. Planar point sets with a small number of empty convex polygons (with I. Barany), Studia Math Hung. 41 (2004), 243-266.
  42. Distributions producing random Voronoi diagrams of large complexity
  43. Three asymptotically equivalent definitions of Davenport-Schinzel trees, submitted
  44. A Ramsey property of planar graphs (with J. Nesetril and J. Solymosi), in: J. Pach (Ed.), Towards a theory of geometric graphs, Contemporary mathematics, Vol. 342, AMS, 2004, pp. 169-176
  45. The unit distance problem on spheres (with K. Swanepoel), in: J. Pach (Ed.), Towards a theory of geometric graphs, Contemporary mathematics, Vol. 342, AMS, 2004, pp. 273-279
  46. On the positive fraction Erdos-Szekeres theorem for convex sets (with A. Por), European Journal of Combinatorics 27 (2006), 1199-1205.
  47. The Erdos-Szekeres theorem: upper bounds and related results (with G. Toth), in: J. E. Goodman, J. Pach, and E. Welzl (Eds.), Combinatorial and Computational Geometry, MSRI Publications 52 (2005), 557-568.
  48. On the Pair-Crossing Number, in: J. E. Goodman, J. Pach, and Emo Welzl (Eds.), Combinatorial and Computational Geometry, MSRI Publications 52 (2005), 569-575.
  49. On edges crossing few other edges in simple topological complete graphs (with J. Kyncl), Discrete Math. 309, No. 7, 1917-1923 (2009); an earlier version in Proc. Graph Drawing 2005, Limerick, Ireland, Lecture Notes in Computer Science 3843 (2006), pp. 274-284.
  50. Open caps and cups in planar point sets, Discrete and Computational Geometry 37 (2007), 565-576.
  51. Labelings of graphs with fixed and variable edge-weights (with R. Babilon, V. Jelinek, and D. Kral), SIAM J. on Discrete Math. 21 (2007), 688-706.
  52. Empty convex polygons in almost convex sets (with G. Lippner and Gy. Karolyi), Periodica Mathematica Hungarica 55 (2007), 121-127.
  53. Universal Sets for Straight-Line Embeddings of Bicolored Graphs (with J. Cibulka, J. Kyncl, V. Meszaros, R. Stolar), J. Pach (Ed.), Thirty Essays on Geometric Graph Theory, Algorithms and Combinatorics, pp. 101-119, Springer, 2013, ISBN 978-1-4614-0109-4. An extended abstract of an earlier version: Hamiltonian alternating paths on bicolored double-chains (with J. Cibulka, J. Kyncl, V. Meszaros, and R. Stolar), Lecture Notes in Computer Science, Volume 5417 (Proc. Graph Drawing '08), pp. 181-192 (2009).
  54. The partitioned Erdos-Szekeres theorem for convex sets (with A. Por), in preparation
  55. Traversing a set of points with a minimum number of turns (with S. Bereg, P. Bose, A. Dumitrescu, and F. Hurtado), Discrete Comput. Geom. 41 (1) (2009), 513-532; a preliminary version in Proceedings of the 23rd ACM Symposium on Computational Geometry, pp. 46-55, ACM, 2007.
  56. Strictly convex norms allowing many unit distances and related touching questions, submitted
  57. On Empty Hexagons, in: J. E. Goodman, J. Pach, and R. Pollack, Surveys on Discrete and Computational Geometry, Twenty Years Later, Contemp. Math. 453, AMS, 2008, pp. 433-441.
  58. On triconnected and cubic plane graphs on given point sets (with A. García, F. Hurtado, C. Huemer, and J. Tejel), Computational Geometry: Theory and Applications 42 (2009), 913-922.
    (An earlier and different version: On embedding triconnected cubic graphs on point sets (with A. García, F. Hurtado, C. Huemer, and J. Tejel), extended abstract in: Electronic Notes in Discrete Mathematics 29 (2007), 531-538)
  59. I. Barany, A. Por, P. Valtr: Paths with no small angles, Proceedings of the 8th Latin American conference on Theoretical informatics 2008 (Latin 08), pp. 654-663 (2008); SIAM J. Discrete Math. 23(4): 1655-1666 (2009)
  60. Cs. D. Tóth and P. Valtr, Augmenting the edge connectivity of planar straight line graphs to three, Proc. of XIII Encuentros de Geometría Computacional 2009, Zaragoza, 6 pages, 2009.
  61. M. Al-Jubeh, M. Ishaque, K. Redei, D.L. Souvaine, C.D. Toth, and P. Valtr: Augmenting the edge connectivity of planar straight line graphs, Algorithmica 61 (2011), 971-999 (partially overlapping with the previous conference paper)
  62. S. Felsner and P. Valtr, Coding and Counting Arrangements of Pseudolines, Discrete and Computational Geometry: Volume 46, Issue 3 (2011), pages 405-416 (extended abstract in Proceedings of EuroCG 2010, 157-160).
  63. K. J. Swanepoel and P. Valtr, Large convexly independent subsets of Minkowski sums, Electronic J. Comb. 17 (2010), R146, 1-7
  64. J. Cibulka, J. Kyncl, V. Mészáros, R. Stolar, P. Valtr: On three parameters of invisibility graphs (with J. Cibulka, V. Meszaros, R. Stolar and P. Valtr), extended abstract in: Computing and Combinatorics (proceedings of COCOON 2010), Lecture Notes in Computer Science 6196, 192-198, Springer, 2010.
  65. J. Cibulka, J. Kyncl, V. Mészáros, R. Stolar, P. Valtr: Graph sharing games: complexity and connectivity, Theoretical Computer Science 494 (2013), 49-62; extended abstract in: TAMC 2010, Lecture Notes in Computer Science 6108, 340-349, Springer, 2010
  66. J. Cibulka, J. Kyncl, V. Mészáros, R. Stolar, P. Valtr: Solution of Peter Winkler's pizza problem, in: G. Katona, A. Schrijver, T. Szönyi (Eds.), Fete of Combinatorics and Computer Science, 63-93, Springer, 2010; extended abstract in: Combinatorial Algorithms (proceedings of IWOCA 2009), Lecture Notes in Computer Science 5874, 356-367, Springer, Berlin, 2009
  67. Birgit Vogtenhuber, Oswin Aichholzer, Ruy Fabila-Monroy, Clemens Huemer, Jorge Urrutia, Marco A. Heredia, Hernan Gonzalez-Aguilar, Thomas Hackl, and Pavel Valtr: On k-gons and k-holes in point sets, Comput. Geom. 48(7): 528-537 (2015), also Proceedings of 23rd Canadian Conference on Computational Geometry (CCCG 2011), August 2011, pp. 21-26
  68. Michael S. Payne, Attila Por, Pavel Valtr and David R. Wood: On the connectivity of visibility graphs, Discrete and Computational Geometry 48, Issue 3 (2012), 669-681.
  69. P. Valtr, On empty pentagons and hexagons in planar point sets, In Proc. Computing: The Australasian Theory Symposium (CATS 2012) Melbourne, Australia. CRPIT, Vol. 128, J. Mestre (editor), ACS, pp. 47-48
  70. Jens M. Schmidt and Pavel Valtr, Cubic Plane Graphs on a Given Point Set, Proc. SoCG 2012, pp. 201-208 and Comput. Geom. 48(1): 1-13 (2015)
  71. J. Barat, V. Dujmovic, G. Joret, M. Payne, L. Scharf, D. Schymura, P. Valtr, D. R. Wood: Empty pentagons in point sets with collinearities, SIAM J. Discrete Math. 29.1:198-209, 2015
  72. S. Felsner, M. Kaufmann, P. Valtr: Bend-optimal orthogonal graph drawing in the general position model, Computational Geometry: Theory and Applications 47 (2014), Issue 3, Pages 460-468 (extended abstract appeared in Proc. EuroCG 2012, pp. 153-156)
  73. Josef Cibulka, Jan Kyncl and Pavel Valtr: On planar point sets with the pentagon property, Proc. SoCG 2013, pp. 81-90
  74. Oswin Aichholzer, Jean Cardinal, Vincent Kusters, Stefan Langerman, and Pavel Valtr. Reconstructing Point Set Order Types from Radial Orderings. In Algorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, pages 15-26, 2014 also Int. J. Comput. Geometry Appl. 26(3-4): 167-184 (2016)
  75. O. Aichholzer, F. Aurenhammer, T. Hackl, F. Hurtado, A. Pilz, P. Ramos, J. Urrutia, P. Valtr, and B. Vogtenhuber. On k-Convex Point Sets. Computational Geometry: Theory and Applications, 47(8):809-832, 2014.
  76. Oswin Aichholzer, Ruy Fabila-Monroy, Hernan Gonzalez-Aguilar, Thomas Hackl, Marco A. Heredia, Clemens Huemer, Jorge Urrutia, Pavel Valtr, and Birgit Vogtenhuber. On k-Gons and k-Holes in Point Sets. Computational Geometry: Theory and Applications, 48(7):528-537, 2015.
  77. Sergio Cabello, Josef Cibulka, Jan Kyncl, Maria Saumell and Pavel Valtr: Peeling potatoes near-optimally in near-linear time, SIAM J. Comput. 46(5): 1574-1602 (2017), also Proc. SoCG 2014, ACM, New York, NY, USA, Pages 224-231.
  78. Oswin Aichholzer, Thomas Hackl, Pavel Valtr, Birgit Vogtenhuber: A Note on the Number of General 4-holes in (Perturbed) Grids. JCDCGG 2015, Name Lecture Notes in Computer Science (LNCS) 9943: 1-12 (2015)
  79. Martin Balko and Pavel Valtr: A SAT attack on the Erdős-Szekeres conjecture, Eur. J. Comb. 66: 13-23 (2017), also Electronic Notes in Discrete Mathematics 49, pages 425-431, 2015.
  80. Josef Cibulka, Pu Gao, Marek Krcál, Tomás Valla, Pavel Valtr: On the Geometric Ramsey Number of Outerplanar Graphs. Discrete and Computational Geometry 53(1): 64-79 (2015)
  81. Vít Jelínek, Pavel Valtr: Splittings and Ramsey properties of permutation classes. Adv. Appl. Math. 63: 41-67 (2015)
  82. Martin Balko, Josef Cibulka, and Pavel Valtr, Drawing graphs using a small number of obstacles, Discrete and Computational Geometry 59(1), pages 143-164, 2018, also Proceedings of 23rd International Symposium on Graph Drawing and Network Visualization (Graph Drawing 2015), Lecture Notes in Computer Science, pages 360-372, 2015 (best paper award).
  83. Patrizio Angelini, Michael A. Bekos, Till Bruckdorfer, Jaroslav Hancl, Michael Kaufmann, Stephen G. Kobourov, Antonios Symvonis, Pavel Valtr: Low Ply Drawings of Trees. Graph Drawing 2016: 236-248
  84. O. Aichholzer, M. Balko, T. Hackl, A. Pilz, P. Ramos, B. Vogtenhuber, and P. Valtr, Holes in 2-convex point sets, Computational Geometry: Theory and Applications 74, pages 38-49, 2018, also Proceedings of the 28th International Workshop on Combinatorial Algorithms (IWOCA 2017), Lecture Notes in Computer Science, vol 10765. Springer, Cham, pages 169-181, 2018.
  85. Martin Balko, Vit Jelinek, Pavel Valtr, Bartosz Walczak: On the Beer Index of Convexity and Its Variants. Symposium on Computational Geometry 2015: 406-420; journal version: Discrete and Computational Geometry 57,1 (2017),179-214.
  86. Markus Chimani, Stefan Felsner, Stephen G. Kobourov, Torsten Ueckerdt, Pavel Valtr, Alexander Wolff: On the Maximum Crossing Number. J. Graph Algorithms Appl. 22(1): 67-87 (2018), also IWOCA 2017: 61-74
  87. M. Balko, J. Cibulka and P. Valtr. Covering lattice points by subspaces and counting point-hyperplane incidences, Discret. Comput. Geom. 61(2): 325-354 (2019), also Symposium on Computational Geometry 2017: 12:1-12:16.
  88. Patrizio Angelini, Steven Chaplick, Felice De Luca, Jiri Fiala, Jaroslav Hancl, Niklas Heinsohn, Michael Kaufmann, Stephen G. Kobourov, Jan Kratochvil, Pavel Valtr: On Vertex- and Empty-Ply Proximity Drawings. Graph Drawing 2017: 24-37
  89. Martin Balko, Vít Jelínek, Pavel Valtr: On ordered Ramsey numbers of bounded-degree graphs. J. Comb. Theory, Ser. B 134: 179-202 (2019)
  90. John Gimbel, Patrice Ossona de Mendez, Pavel Valtr: Obstacle Numbers of Planar Graphs. Graph Drawing 2017: 67-80
  91. Josef Cibulka, Miroslav Korbelár, Jan Kyncl, Viola Mészáros, Rudolf Stolar, Pavel Valtr. On three measures of non-convexity. Israel Journal of Mathematics 218 (2017), Issue 1, 331-369
  92. Oswin Aichholzer, Martin Balko, Thomas Hackl, Jan Kyncl, Irene Parada, Manfred Scheucher, Pavel Valtr, Birgit Vogtenhuber: A Superlinear Lower Bound on the Number of 5-Holes. J. Comb. Theory, Ser. A 173 (2020), also Symposium on Computational Geometry 2017: 8:1-8:16
  93. Michael Kaufmann, Jan Kratochvíl, Fabian Lipp, Fabrizio Montecchiani, Chrysanthi N. Raftopoulou, Pavel Valtr: Bounded Stub Resolution for Some Maximal 1-Planar Graphs. CALDAM 2018: 214-220
  94. Michael Kaufmann, Jan Kratochvíl, Fabian Lipp, Fabrizio Montecchiani, Chrysanthi N. Raftopoulou, Pavel Valtr: The Stub Resolution of 1-Planar Graphs. Proc. WALCOM 2020: 170-182
  95. Ruy Fabila Monroy, Jakob Jonsson, Pavel Valtr, David R. Wood: The exact chromatic number of the convex segment disjointness graph (manuscript)
  96. Vít Jelínek, Michal Opler, Pavel Valtr: Generalized Coloring of Permutations. ESA 2018: 50:1-50:14
  97. Man-Kwun Chiu, Stefan Felsner, Manfred Scheucher, Patrick Schnider, Raphael Steiner, Pavel Valtr: On the Average Complexity of the k-Level. Full version in Journal of Computational Geometry 11(1), pages 493-506, 2020. Extended Abstract in Proceedings of the 36th European Workshop on Computational Geometry (EuroCG), 2020.
  98. Martin Balko, Sujoy Bhore, Leonardo Martínez-Sandoval, Pavel Valtr: On Erdos-Szekeres-Type Problems for k-convex Point Sets. Eur. J. Comb. 89: 103157 (2020) (conference version: IWOCA 2019: 35-47)
  99. Markus Chimani, Philipp Kindermann, Fabrizio Montecchiani, Pavel Valtr: Crossing Numbers of Beyond-Planar Graphs. GD 2019: 78-86
  100. Oswin Aichholzer, Martin Balko, Michael Hoffmann, Jan Kyncl, Wolfgang Mulzer, Irene Parada, Alexander Pilz, Manfred Scheucher, Pavel Valtr, Birgit Vogtenhuber, Emo Welzl: Minimal Representations of Order Types by Geometric Graphs. GD 2019: 101-113
  101. Radoslav Fulek, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, Uli Wagner: The Crossing Tverberg Theorem. Symposium on Computational Geometry 2019: 38:1-38:13
  102. Martin Balko,Attila Por,Manfred Scheucher,Konrad Swanepoel,Pavel Valtr: Almost-Equidistant Sets, Graphs and Combinatorics 36:729-755, 2020
  103. Martin Balko, Manfred Scheucher, Pavel Valtr: Holes and islands in random point sets. Proceedings of the 36th International Symposium on Computational Geometry (SoCG 2020), pages 14:1-14:16, LIPIcs 164, Dagstuhl, 2020.
  104. Wolfgang Mulzer, Pavel Valtr: Long Alternating Paths Exist, Proceedings of the 36th International Symposium on Computational Geometry (SoCG 2020), pages 57:1-57:16, LIPIcs 164, Dagstuhl, 2020.

If you are interested in getting some of my papers, send me an e-mail.

Email: "surname"@kam.mff.cuni.cz