List of publications and manuscripts (Pavel Valtr)
Mathematical Reviews (results for ''author = Valtr'')
Papers and manuscripts
 Convex independent sets and 7holes in restricted planar point sets,
Discrete and Computational Geometry 7 (1992), 135152
 Sets in $R^d$ with no large empty convex subsets,
Discrete Mathematics 108 (1992), 115124
 Generalized DavenportSchinzel sequences with linear upper bound
(with R. Adamec and M. Klazar),
Discrete Mathematics 108 (1992), 219229
 A Ramseytype theorem in the plane (with
J. Nesetril),
Combinatorics, Probability and Computing 3 (1994), 127135
 Unit squares intersecting all secants of a square,
Discrete and Computational Geometry 11 (1994), 235239
 Cutting dense point sets in half
(with H. Edelsbrunner and E. Welzl),
Proc. Tenth Annual Symp. on Comp. Geom.,
Stony Brook, ACM Press (1994), 203210;
also Discrete and Computational Geometry 17 (1997), 243255
 Generalized DavenportSchinzel sequences
(with M. Klazar),
Combinatorica 14 (1994), 463476
 Probability that $n$ random points are in convex position,
Discrete and Computational Geometry 13 (1995), 637643
 On the minimum number of empty polygons in planar point sets,
Studia Scientiarum Mathematicarum Hungarica 30 (1995), 155163
 Ramseyremainder
(with P. Erdös and Zs. Tuza),
European Journal of Combinatorics 17 (1996), 519532
 Lines, linepoint incidences and crossing families in dense sets,
DIMACS Technical Report 9455 or Combinatorica 16 (1996), 269294
 The probability that $n$ random points in a triangle are in convex position (abstract),
Combinatorica 16 (1996), 567573
 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), 324332
 Catalan numbers via random planar point sets,
Intuitive Geometry (I. Barany, ed.), Bolyai Society Math. Studies 6 (1997),
441443
 Graph drawings with no $k$
pairwise crossing edges,
in: G. DiBattista (ed.), Graph Drawing '97, Rome, September 1997, pp. 205218
 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),
407411

Ramseytype results for geometric graphs, II
(with Gy. Karolyi, J. Pach, and G. Toth),
DIMACS Technical Report 9713,
Discrete and Computational Geometry 20 (1998), 375388.
 Guarding galleries where no point sees a small area,
Israel Journal of Mathematics 104 (1998), 116

On the density of subgraphs in a graph with bounded
independence number
DIMACS Technical Report 9711
and J. Comb. Th., Ser. B, 73 (1998), 146158.
 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. 3744.
 A Ramsey property of order types
(with J. Nesetril),
J. of Comb. Th. (Ser. A) 81 (1998), 88107.
 A positive fraction ErdosSzekeres theorem
(with I. Barany),
Discrete and Computational Geometry 19 (1998), 335342.

On geometric graphs with no $k$
pairwise parallel edges,
DIMACS Technical Report 9707 ,
Discrete and Computational Geometry 19 (1998), 461469.

Note on the ErdosSzekeres theorem
(with G. Toth),
Discrete and Computational Geometry 19 (1998), 457459,
DIMACS Technical Report 9731.

Geometric graphs with few disjoint edges
(with G. Toth),
Discrete Comput. Geom. 22 (1999), 633642
(also Proc. of Ann. Symp. Comput. Geom. 1998, pp. 181194).

The largest $k$ball in a $d$dimensional box
(with H. Everett, I. Stojmenovic, and S. Whitesides),
Computational Geometry: Theory and Applications 11 (1998),
5967

On an extremal problem for colored trees,
Europ. J. Comb. 20 (1999), 115121

On galleries with no bad points,
DIMACS Technical Report 9655, Discrete
and Computational Geometry 21 (1999), 193200.

Generalizations of DavenportSchinzel 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), 349389.

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), 219227

Almosttiling the plane by ellipses
(with K. Kuperberg, W. Kuperberg, and J. Matousek),
Discrete and Computational Geometry 22 (1999), 367375.
 On visibility and covering by convex sets
(with J. Matousek),
Israel Journal of Mathematics 113 (1999), 341379.

Lowdistortion embeddings of trees
(with R. Babilon,
J. Matousek, and J. Maxova), Graph Drawing 2001,
Lecture Notes in Comp. Sci. 2265, Springer 2002,
pp. 343351.

The partitioned version of the ErdosSzekeres theorem
(with A. Por), Discrete and Computational Geometry
28 (2002), 625637.

A sufficient condition for the existence of
large empty convex polygons,
Discrete and Computational Geometry 28 (2002),
671682

One line and n points
(with B. Gartner, J. Solymosi, F. Tschirschnitz,
and E. Welzl), Random Structures and Algorithms 23 (2003),
453471.

DavenportSchinzel trees,
Combinatorica 23 (2003), 151184

Point configurations in $d$space without
large subsets in convex position
(with Gy. Karolyi), Discrete and Computational Geometry 30 (2003), 277286.

A Turantype extremal theory of convex geometric
graphs
(with P. Brass and Gy. Karolyi), in: B. Aronov et al. (Eds.),
Discrete and Computational GeometryThe GoodmanPollack
Festschrift, Springer, Berlin, 2003, pp. 275300.

VCdimension of exterior visibility
(with K. Daniilidis, V. Isler, and S. Kannan), IEEE Transactions
on Pattern Analysis and Machine Intelligence 26 (2004), 667671.

Planar point sets with a small number of empty
convex polygons (with I. Barany), Studia Math Hung. 41 (2004),
243266.

Distributions producing random Voronoi diagrams of large
complexity

Three asymptotically equivalent definitions
of DavenportSchinzel trees,
submitted

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. 169176

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. 273279

On the positive fraction
ErdosSzekeres theorem for convex sets
(with A. Por), European Journal of Combinatorics 27 (2006), 11991205.

The ErdosSzekeres 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), 557568.

On the PairCrossing Number,
in: J. E. Goodman, J. Pach, and Emo Welzl (Eds.),
Combinatorial and Computational Geometry, MSRI Publications 52 (2005),
569575.

On edges crossing few other edges in simple topological complete graphs
(with J. Kyncl), Discrete Math. 309, No. 7, 19171923 (2009);
an earlier version in Proc. Graph Drawing 2005, Limerick, Ireland,
Lecture Notes in Computer Science 3843 (2006), pp. 274284.

Open caps and cups in planar point sets,
Discrete and Computational Geometry 37 (2007), 565576.

Labelings of graphs with fixed and variable edgeweights
(with R. Babilon, V. Jelinek, and D. Kral), SIAM J. on Discrete Math. 21 (2007), 688706.

Empty convex polygons
in almost convex sets (with G. Lippner and Gy. Karolyi),
Periodica Mathematica Hungarica 55 (2007), 121127.

Universal Sets for StraightLine 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. 101119, Springer, 2013, ISBN 9781461401094.
An extended abstract of an earlier version:
Hamiltonian alternating paths on bicolored doublechains
(with J. Cibulka, J. Kyncl, V. Meszaros, and R. Stolar),
Lecture Notes in Computer Science,
Volume 5417 (Proc. Graph Drawing '08), pp. 181192 (2009).

The partitioned
ErdosSzekeres theorem for convex sets
(with A. Por), in preparation

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), 513532;
a preliminary version in Proceedings of the 23rd ACM Symposium
on Computational Geometry, pp. 4655, ACM, 2007.

Strictly convex norms allowing many unit distances
and related touching questions,
submitted

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. 433441.

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), 913922.
(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),
531538)
 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. 654663 (2008); SIAM J. Discrete Math. 23(4): 16551666 (2009)

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.

M. AlJubeh, 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), 971999 (partially overlapping with the previous conference paper)

S. Felsner and P. Valtr, Coding and Counting Arrangements of Pseudolines,
Discrete and Computational Geometry: Volume 46, Issue 3 (2011), pages 405416
(extended abstract in Proceedings of EuroCG 2010, 157160).

K. J. Swanepoel and P. Valtr,
Large convexly independent subsets of Minkowski sums,
Electronic J. Comb. 17 (2010), R146, 17

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, 192198, Springer, 2010.

J. Cibulka, J. Kyncl, V. Mészáros, R. Stolar, P. Valtr:
Graph sharing games: complexity and connectivity, Theoretical Computer Science 494 (2013), 4962;
extended abstract in: TAMC 2010, Lecture Notes in Computer Science 6108, 340349, Springer, 2010

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, 6393, Springer, 2010;
extended abstract in: Combinatorial Algorithms (proceedings of IWOCA 2009), Lecture Notes in Computer Science 5874, 356367, Springer, Berlin, 2009

Birgit Vogtenhuber, Oswin Aichholzer, Ruy FabilaMonroy, Clemens Huemer, Jorge Urrutia, Marco A. Heredia,
Hernan GonzalezAguilar, Thomas Hackl, and Pavel Valtr: On kgons and kholes in point sets, Proceedings of 23rd
Canadian Conference on Computational Geometry (CCCG 2011), August 2011, pp. 2126

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), 669681.

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. 4748

Jens M. Schmidt and Pavel Valtr, Cubic Plane Graphs on a Given Point Set, Proc. SoCG 2012, pp. 201208 and Comput. Geom. 48(1): 113 (2015)

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:198209, 2015.

S. Felsner, M. Kaufmann, P. Valtr: Bendoptimal orthogonal graph drawing in the general position model,
Computational Geometry: Theory and Applications 47 (2014), Issue 3,
Pages 460468 (extended abstract appeared in Proc. EuroCG 2012, pp. 153156)

Josef Cibulka, Jan Kyncl and Pavel Valtr: On planar point sets with the pentagon property, Proc. SoCG 2013, pp. 8190
 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 1517, 2014, Proceedings, pages 1526, 2014.
 O. Aichholzer, F. Aurenhammer, T. Hackl, F. Hurtado, A. Pilz, P. Ramos, J. Urrutia, P. Valtr, and B. Vogtenhuber. On kConvex Point Sets. Computational Geometry: Theory and Applications, 47(8):809832, 2014.
 Oswin Aichholzer, Ruy FabilaMonroy, Hernan GonzalezAguilar, Thomas Hackl, Marco A. Heredia, Clemens Huemer, Jorge Urrutia, Pavel Valtr, and Birgit Vogtenhuber. On kGons and kHoles in Point Sets. Computational Geometry: Theory and Applications, 48(7):528537, 2015.
 Sergio Cabello, Josef Cibulka, Jan Kyncl, Maria Saumell and Pavel Valtr:
Peeling potatoes nearoptimally in nearlinear time, Proc. SoCG 2014, ACM, New York,
NY, USA, Pages 224231.
 Martin Balko and Pavel Valtr: A SAT attack on the ErdősSzekeres conjecture,
Electronic Notes in Discrete Mathematics 49, pages 425431, 2015.
 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): 6479
(2015)
 Martin Balko, Josef Cibulka, and Pavel Valtr, Drawing graphs using a small number of obstacles,
Proceedings of 23rd International Symposium on Graph Drawing & Network Visualization (Graph Drawing 2015), Lecture Notes in Computer Science, pages 360372, 2015 (best paper award).
 O. Aichholzer, M. Balko, T. Hackl, A. Pilz, P. Ramos, B. Vogtenhuber, and P. Valtr,
Holes in 2convex point sets, 32th European Workshop on Computational Geometry (EuroCG 2016),
pages 263266, 2016.
 Martin Balko, Vit Jelinek, Pavel Valtr, Bartosz Walczak:
On the Beer Index of Convexity and Its Variants. Symposium on Computational Geometry 2015: 406420;
journal version: Discrete and Computational Geometry 57,1 (2017),179214.
 O. Aichholzer, M. Balko, T. Hackl, J. Kyncl, I. Parada, M. Scheucher, P. Valtr, and B. Vogtenhuber,
A superlinear lower bound on the number of 5holes, to appear in the Proceedings of the 33rd International Symposium on Computational Geometry (SoCG 2017).
If you are interested in getting some of my papers, send
me an email.
Email: "surname"@kam.mff.cuni.cz