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, 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, 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
  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, submitted (2012)
  72. S. Felsner, M. Kaufmann, P. Valtr: Bend-optimal orthogonal graph drawing in the general position model, submitted (2012) (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, to appear in Proc. SoCG 2013.

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

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