Books



NEW! NEW! P. Brass, W. Moser, J. Pach: Otkrytye Problemy Diskretnoy Geometrii (Open Problems in Discrete Geometry, in Russian)
Publishing House of the Center for Continuing Mathematics Education,
119002 Moscow, Russian Federation, 2021.
book picture New Trends in Intuitive Geometry,
(G. Ambrus, I. Bárány, K. J. Böröczky, G. Fejes Tóth, and J. Pach, editors)
Bolyai Society Mathematical Studies 27,
Springer-Verlag, New York, 2018.
book picture Geometry - Intuitive, Discrete, and Convex,
(I. Bárány, K. J. Böröczky, G. Fejes Tóth, and J. Pach, editors)
Bolyai Society Mathematical Studies 24,
Springer-Verlag, New York, 2013.
book picture J. Pach (Ed.): Thirty Essays in Geometric Graph Theory,
Springer-Verlag, New York, 2013.
J. Pach, M. Sharir: Combinatorial Geometry and Its Algorithmic Applications: The Alcala Lectures,
Math. Surveys and Monographs v. 152,
American Mathematical Society, Providence, 2009.
Twentieth Anniversary Volume: Discrete & Computational Geometry
(J. E. Goodman, J. Pach, and R. Pollack, editors)
Springer-Verlag, Berlin-Heidelberg-New York, 2009.
Surveys on Discrete and Computational Geometry: Twenty Years Later
(J. E. Goodman, J. Pach, and R. Pollack, editors).
Contemporary Mathematics 453, American Mathematical Society, Providence, 2008.
P. Brass, W. Moser and J. Pach: "Research Problems in Discrete Geometry",
Springer-Verlag, New York, 2005.

Facsimile edition: China Science Press, Beijing, 2006
Japanese translation: Springer, Tokyo, 2009.
J.E. Goodman, J. Pach, E. Welz (Eds.) : "Combinatorial and Computational Geometry",
Cambridge University Press, Cambridge, 2005.
J. Pach (Ed.): "Graph Drawing", Springer-Verlag, Berlin, 2005.
cover J. Pach (Ed.): "Towards a Theory of Geometric Graphs",
American Mathematical Society, Providence, 2004.
B. Aronov, S. Basu, J. Pach and M. Sharir (Eds.): "Discrete and Computational Geometry",
Springer-Verlag, Berlin, 2003.
J. Pach and P. Agarwal: "Combinatorial Geometry",
J. Wiley, New York, 1995.

Chinese translation, Chinese Science Press (CSP), Beijing, 2008.
• J. Pach (Ed.): "New Trends in Discrete and Computational Geometry",
Springer-Verlag, Berlin, 1993.


List of publications


[1] On metric properties of countable graphs, Matematikai Lapok 26 (1975), 305-310 (in Hungarian).

[2] On super-universal graphs, Studia Sci. Math. Hung. 12 (1977), 19-27.

[3] On the permeability problem, Studia Sci. Math. Hung. 12 (1977), 419-424.

[4] Random graphs, M. Sc. Thesis, Budapest, 1977 (in Hungarian).

[5] On an isoperimetric problem, Studia Sci. Math. Hung. 13 (1978), 43-45.

[6] Graphs of diameter 2 and linear programming (with L. Surányi), Coll. Math. Soc. J. Bolyai 25. Algebraic Methods in Graph Theory 599-629, North-Holland, 1978.

[7] Note on a problem of Erdős and Katona, Ars Combinatoria 9 (1980), 27-31.

[8] On universal graphs, Ph.D. Thesis, Budapest, 1980 (in Hungarian).

[9] Decomposition of multiple packing and covering, 2. Kolloquium über Diskrete Geometrie, Salzburg (1980), 169-178.

[10] On a problem of L. Fejes Tóth (with P. Erdős), Discrete Mathematics 30 (1980), 103-109.

[11] L. Lovász: Combinatorial Problems and Exercises (Book review). Magyar Tudomány 4 (1980), 313-314.

[12] On graphs of diameter 2 (with L. Surányi), Ars Combinatoria 11 (1981), 61-78.

[13] Graphs whose every independent set has a common neighbour, Discrete Mathematics 37 (1981), 217-228.

[14] A problem of Ulam on planar graphs, European Journal of Combinatorics 2 (1981), 357-361.

[15] Mixed volume and the van der Waerden conjecture, Matematikai Lapok 29 (1981), 49-60 (in Hungarian).

[16] Helly's theorem with volumes (with I. Bárány and M. Katchalski), American Mathematical Monthly, June-July 1984, 362-365.

[17] Quantitative Helly-type theorems (with I. Bárány and M. Katchalski), Proceedings of the Amer. Math. Soc. 86 (1982), 109-114.

[18] Mathematical time bomb, Magyar Tudomány 1981/10, 746-749 (in Hungarian).

[19] On a quasi-Ramsey problem (with P. Erdős), Journal of Graph Theory 7 (1983), 137-147.

[20] Controlling function classes and covering Euclidean space (with E. Makai, Jr.), Studia Math. Sci. Hung., 18 (1983), 435-459.

[21] On the number of sets in a null-t-design (with P. Frankl), European Journal of Combinatorics 4/1 (1983), 21-23.

[22] Partly convex Peano curves (with C. A. Rogers), Bulletin of the London Math. Soc. 15 (1983), 321-328.

[23] Advanced Problem No. 6421 (with J. Beck and F. Galvin), American Math. Monthly 90 (1983), 134.

[24] Monochromatic paths in infinite coloured graphs (with A. Hajnal) Coll. Math. Soc. J. Bolyai 37, Finite and Infinite Sets (A. Hajnal et. al. eds), North-Holland, Amsterdam, 1984, 359-364.

[25] On locally Hamiltonian graphs (with G. O. H. Katona, A. Kostochka and B. Stechkin), Mat. Zametki 45 (1989), 36-42.



[26] Discrete convex functions and proof of the six circle conjecture of Fejes Tóth (with I. Bárány and Z. Füredi), Can. J. Math. 36 (1984), 569-576.

[27] On disjointly representable sets (with P. Frankl), Combinatorica 4 (1984), 39-45.

[28] The Analysis Incarnate -- Leonhard Euler, Magyar Tudomány 1984/3, 203-223 (in Hungarian).

[29] The Mathematician of the Enlightenment, Középiskolai Matematikai Lapok 34 (1984), 1-3 (in Hungarian).

[30] Remarks on stars and independent sets (with P. Erdős), in: Aspects of Topology (I. M. James and E. H. Kronheimer, eds.), Cambridge University Press, 1984, 307-314.

[31] A point set everywhere dense in the plane (with K. Bezdek), Elemente der Mathematik, 40 (1985), 81-84.

[32] How to build a barricade (with P. Frankl and V. Rödl), Monatshefte für Mathematik 93 (1984), 93-98.

[33] Maximal volume enclosed by plates and proof of the chessboard conjecture (with I. Bárány, K. Böröczky and E. Makai, Jr.), Discr. Math. 60 (1986), 101-120.

[34] Universal graphs without large bipartite subgraphs (with P. Komjáth), Mathematika, 31 (1984), 282-290.

[35] 2-super-universal graphs (with L. Surányi), Proceedings of the Fourth International Graph Theory Conference, Kalamazoo, 1984, John Wiley (1985), 623-636.

[36] Bounding one-way differences (with P. Frankl and Z. Füredi), Graphs and Combinatorics 3 (1987), 341-347.

[37] Covering the plane with convex polygons, Discr. and Comput. Geometry 1 (1986), 73-81.

[38] On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles (with K. Kedem, R. Livne and M. Sharir), Discr. and Comput. Geometry 1 (1986), 59-71.

[39] How to make a graph bipartite (with P. Erdős, R. Faudree and J. Spencer), J. Combin. Th. Series B 45 (1988), 86-98.

[40] On the mean distance between points of a graph (with P. Erdős and J. Spencer), 250th Anniversary Conference on Graph Theory (Fort Wayne, 1986), Congressus Numerantium 64 (1988), 121-124.

[41] On the big unsolved problems in elementary geometry, Magyar Tudomány 1986/2, 120-131 (in Hungarian).

[42] Cutting a graph into dissimilar halves (with P. Erdős, M. Goldberg and J. Spencer), J. Graph Theory 12 (1988), 121-131.

[43] An upper bound for families of linearly related plane convex sets (with T. Bisztriczky), Archiv der Math. 50 (1988), 56-58.

[44] Repeated distances in space (with D. Avis and P. Erdős), Graphs and Combinatorics 4 (1988), 207-217.

[45] 100 Research Problems in Discrete Geometry (with W. O. J. Moser), mimeographed .
Research Problems in Discrete Geometry (with P. Brass and W. Moser), Springer-Verlag, New York, 2005.

[46] Note on vertex-partitions of infinite graphs (with J. Spencer), Discr. Math. 79 (1989/90), 107-108.

[47] Explicit codes with low covering radius (with J. Spencer), IEEE Transactions of Information Theory 34 (1988), 1281-1285.

[48] An extremal problem on Kr-free graphs (with P. Frankl), J. Graph Theory 12 (1988), 519-523.

[49] Decomposition problems for multiple coverings with unit balls (with P. Mani), manuscript.



[50] Radius, diameter and minimum degree (with P. Erdős, R. Pollack and Zs. Tuza), Journal of Combinatorial Theory B 47 (1989), 73-79.

[51] Mountain climbing, ladder moving, and the ring width of a polygon (with J. E. Goodman and Chee K. Yap), Amer. Math. Monthly 96 (1989), 494-510.

[52] On the lower envelope of bivariate functions and its applications (with H. Edelsbrunner, J. T. Schwartz and M. Sharir), Proc. 28th FOCS Symposium 1987, 27-38.

[53] Some universal graphs (with P. Komjáth and A. H. Mekler), Israel Journal of Mathematics 64 (1988), 158-168.

[54] On arrangements of Jordan arcs with three intersections per pair (with H. Edelsbrunner, L. Guibas, J. Hershberger, R. Pollack, R. Seidel, M. Sharir and J. Snoeyink), Proc. 4th ACM Symposium on Computational Geometry, 1988, 258-265.
See also Discrete and Comp. Geom. 4 (1989), 523-539.

[55] Arrangements of curves in the plane - Topology, Combinatorics and Algorithms (with H. Edelsbrunner, L. Guibas, R. Pollack, R. Seidel and M. Sharir). '88 ICALP Proc. 214-229.
Also in: Theoretical Computer Science 92 (1992), 319-336.

[56] A problem of Leo Moser about repeated distances on the sphere (with P. Erdős and D. Hickerson), Amer. Math. Monthly 96 (1989), 569-575.

[57] Small sets supporting Fáry embeddings of planar graphs (with H. de Fraysseix and R. Pollack), 20th STOC Symposium 1988, 426- 433.
Almost identical with: How to draw a planar graph on a grid, Combinatorica 10 (1990), 41-51.

[58] The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis (with M. Sharir), Discrete and Computational Geom. 4. (1989), 291-309.

[59] Delicate symmetry, Computers and Mathematics with Applications 17 (1989), 117-124.

[60] Isomorphic subgraphs in a graph (with P. Erdős and L. Pyber), in: Combinatorics, Coll. Math. Soc. J. Bolyai 52 (1988), 553-556.

[61] On the average volume of subsets in Euclidean d-space (with N. Sauer), European J. Combinatorics 12 (1991), 417-421.

[62] Problem on convex polygons, James Cook Math. Notes 5 (1988), 5116-5117.

[63] Cell decomposition of polygons by bending (with J. E. Goodman), Israel J. Math. 64 (1988), 129-138.

[64] On vertical visibility in arrangements of segments and the queue size in the Bentley-Ottman line sweeping algorithm (with M. Sharir), SIAM J. Computing 20 (1991), 460-470.

[65] Embedding a planar triangulation with vertices at specified points (with P. Gritzmann, B. Mohar, and R. Pollack), Amer. Math. Monthly 98 (1991), 165-166.

[66] On the game of Misery, Studia Sci. Math. Hung. 27 (1992), 353-358.

[67] On the maximal number of certain subgraphs in Kr-free graphs (with E. Győri and M. Simonovits), Graphs and Combinatorics 7 (1991), 31-37.

[68] Large discs in convex unions (with C. A. Rogers), American Math. Monthly 95 (1988), 765-767.

[69] Variations on the theme of repeated distances (with P. Erdős), Combinatorica 10 (1990), 261-269.

[70] On the structure of a system of stars in graphs (Russian, with Armenian summary), Mat. Voprosy Kibernet. Vychisl. Tekhn. 15 (1988), 165-173 (MR 90j:05079).

[71] An upper bound on the number of planar k-sets (with W. Steiger and E. Szemerédi), Proc. 30th FOCS Symposium, l989, 72-81.
Also in: Discrete Comput. Geom. 7 (1992), 109-123.

[72] Towards a new geometry, Magyar Tudomány 1990/8, 895-903 (in Hungarian).

[73] Weaving patterns of lines and line segments in space (with R. Pollack and E. Welzl), Proc. SIGAL Internat. Symposium on Algorithms, Tokyo Lecture Notes in Comp. Sci. 450 (1990), 439-446, Springer. Also in: Algorithmica 9 (1993), 561-571.

[74] Graph distance and Euclidean distance on the grid (with R. Pollack and J. Spencer), Topics in Graph Theory and Combinatorics, The Ringel-Festzeitschrift (R. Bodendiek, R. Henn, eds), Physica-Verlag, Heidelberg, 1990, 553-559.




[75] Some new bounds for epsilon-nets (with G. Woeginger), Proc. 6th ACM Symposium on Comput. Geom., 1990, 10-15.
See also: Almost tight bounds on epsilon-nets (with J. Komlós and G. Woeginger), Discr. Comput. Geom. 7 (1992), 163-173.

[76] Universal elements and the complexity of certain classes of infinite graphs (with P. Komjáth), in: Directions in Infinite Graph Theory (R. Diestel, ed.), Discr. Math. 95 (1991), 255-270.

[77] On the combinatorial complexity of the space of hyperplane transversals (with S.E. Cappell, J.E. Goodman, R. Pollack, M. Sharir, R. Wenger), Proc. 6th ACM Symposium on Comput. Geom., 1990, 83-91.
Expanded version: Common tangents and common transversals, Advances of Math. 106 (1994), 198-215.

[78] Repeated angles in the plane and related problems (with M. Sharir), J. Combinat. Theory Ser. A 59 (1992), 12-22.

[79] Gaps in difference sets, and the graph of nearly equal distances (with P. Erdős, E. Makai and J. Spencer), in: The Victor Klee Festschrift (P. Gritzmann, B. Sturmfels, eds), DIMACS Series, Vol. 4, Amer. Math. Soc., Providence, 1991, 265-273.

[80] A Turán-type theorem on chords of a convex polygon (with V. Capoyleas), J. Combinat. Theory, Ser B 56 (1992), 9-15.


[81] Recent developments in combinatorial geometry (with W. Moser), in: New Trends in Discrete and Computational Geometry (J. Pach, ed.), Springer-Verlag, Berlin-Heidelberg-New York, 1993, 281-302.

[82] Fat triangles determine linearly many holes (with J. Matousek, N. Miller, M. Sharir, S. Sifrony and E. Welzl), FOCS, Proc. 32nd Symposium, 1991, 49-58.
Also in: SIAM J. Computing 23 (1994), 154-169.

[83] Distinct distances determined by subsets of a point set in space (with D. Avis and P. Erdős), Computational Geometry: Theory and Applications 1 (1991), 1-11.

[84] On the perimeter of a point set in the plane (with V. Capoyleas), Proc. 3rd Canadian Conference on Comput. Geom. (1991) 54-57.
Also in: Discrete and Computational Geometry (J.E. Goodman et al, eds), DIMACS 6 (1991), 67-76.

[85] Separating bi-chromatic points by parallel lines (with T. Asano, J. Hershberger, E. Sontag, D. Souvaine and S. Suri), Proc. 2nd Canadian Conference on Computational Geom., University of Ottawa, Ontario, 1990, 46-49.

[86] Crossing families (with B. Aronov, P. Erdős, W. Goddard, D.J. Kleitman, M. Klugerman, L.J. Schulman), Proc. 7th ACM Symposium on Comput. Geom., 1991, 351-356.
Also in: Combinatorica 14 (1994), 127-134.


[87] The grid revisited, (with P. Erdős, Z. Füredi, I.Z. Ruzsa), Proc. Symp. on Combinatorics and Graph Theory, Marseille, 1990, Discrete Mathematics 111 (1993), 189-196.

[88] The complexity of a class of infinite graphs (with P. Komjáth), Combinatorica 14 (1994), 121-125.


[89] Touching convex sets in the plane (with M. Katchalski), Bull. Canad. Math. Soc. 37 (1994), 495-504.

[90] Layout of rooted trees (with J. Törőcsik), in: Planar Graphs (W.T. Trotter, ed.), DIMACS Series, Vol. 9, Amer. Math. Soc., Providence, 1993, 131-137.

[91] Combinatorial Geometry (with P.K. Agarwal), J. Wiley, New York, 1995. Chinese translation: Chinese Science Press, Beijing, 2008.

[92] Notes on geometric graph theory, in: Discrete and Computational Geometry (J.E. Goodman et al, eds.), DIMACS Series, Vol 6, Amer. Math. Soc., Providence, 1991, 273-285.

[93] On the number of convex lattice polygons (with I. Bárány), Combinatorics, Probability and Computing 1 (1992), 295-302.

[94] An invariant property of balls in arrangements of hyperplanes (with B. Aronov, D. Naiman, M. Sharir), Discrete Comput. Geom. 10 (1993), 421-425.

[95] Sphere-of-influence graphs in higher dimensions (with L. Guibas, M. Sharir), in: Intuitive Geometry (K. Böröczky, G. Fejes Tóth, eds), Coll. Math. Soc. J. Bolyai 63, North-Holland, Amsterdam, 1994, 131-137.

[96] A Ramsey-type result for planar convex sets (with D. Larman, J. Matoušek, J. Törőcsik), Bull. London Math. Soc. 26 (1994), 132-136.


[97] How hard is halfspace range searching? (with H. Brönnimann, B. Chazelle), Discrete Computational Geometry 10 (1993), 143-155.

[98] Traces of finite sets: extremal problems and geometric applications (with Z. Füredi), in: Extremal Problems for Finite Sets, Visegrád 1991, Bolyai Society Mathematical Studies, Vol. 3, Bolyai Society, Budapest, 1994, 251-282.

[99] Uniformly distributed distances -a geometric application of Janson's inequality (with J. Spencer), Combinatorica 19 (1999), 111-124.


[100] Representation of planar graphs by segments (with H. de Fraysseix, P. O. de Mendez), in: Intuitive Geometry (K. Böröczky, G. Fejes Tóth, eds), Coll. Math. Soc. J. Bolyai 63, North-Holland, Amsterdam, 1994, 109-117.



[101] Some geometric applications of Dilworth's theorem (with J. Törőcsik), Proc. 9th ACM Symposium on Computional Geometry 1993, 264-269.
Also in: Discrete and Computational Geometry 12 (1994), 1-7.

[102] A left-first search algorithm for planar graphs (with H. de Fraysseix, P. O. de Mendez), Discrete and Computational Geometry 13 (1995), 459-468.


[103] Nearly equal distances in the plane (with P. Erdős, E. Makai), Combinatorics, Probability and Computing 2 (1993), 401-408.
See also: Solution to Problem 1 of the 1993 Schweitzer Mathematical Competition, Matematikai Lapok 3 (1993), 31-33 (in Hungarian).


[104] Rich cells in an arrangement of hyperplanes (with I. Bárány, H. Bunting, D. Larman), Linear Algebra and its Applications 226-228 (1995), 567-576.


[105] Applications of the crossing number (with F. Shahrokhi, M. Szegedy), Proc. 10th ACM Symposium on Computational Geometry, 1994, 198-202.
Also in: Algorithmica 16 (1996), 111-117.


[106] A remark on transversal numbers, in: The Mathematics of Paul Erdős, Vol. II, (R. L. Graham and J. Nešetřil, eds.), Algorithms and Combinatorics 14, Springer-Verlag, Heidelberg, 1997, 310-317.


[107] Extremal problems for geometric hypergraphs (with T.K. Dey), in: Algorithms and Computation (Proc. ISAAC '96, Osaka; T. Asano et al., eds.), Lecture Notes in Computer Science 1178, Springer-Verlag, 1996, 105-114.
Also in: Discrete and Computational Geometry 19 (1998), 473-484.


[108] On circumscribing polygons for line segments (with E. Rivera-Campo), Computational Geometry: Theory and Applications 10 (1998), 121-124.

[109] On Conway's thrackle conjecture (with L. Lovász, M. Szegedy), Proc. 11th ACM Symposium on Computational Geometry, 1995, 147-151.
Also in: Discrete and Computational Geometry 18 (1997), 369-376.


[110] Quasi-planar graphs have a linear number of edges (with P.K. Agarwal, B. Aronov, R. Pollack, M. Sharir), Proc. Graph Drawing '95, Passau (Franz J. Brandenburg, ed.), Lecture Notes in Computer Science 1027, Springer-Verlag, Berlin, 1996, 1-7.
Also in: Combinatorica 17 (1997), 1-9.


[111] Finite point configurations, Chapter 1 in: Handbook of Discrete and Computational Geometry (J.E. Goodman
and J. O'Rourke, eds.), CRC Press, Boca Raton, 1997, 3-18.


[112] Ramsey-type results for geometric graphs. I (With G. Károlyi, G. Tóth), 12th ACM Symposium on Computational Geometry, 1996, 359-365.
Also in: Discrete and Computational Geometry 18 (1997), 247-255.


[113] On a metric generalization of Ramsey's theorem (with P. Erdős, A. Hajnal), Israel Journal of Mathematics 102 (1997), 283-295.


[114] The hippocampus as a cognitive graph (with R.U. Muller, M. Stead), Journal of General Physiology 107 (1996), 663-694.

[115] A Tverberg-type result on multicolored simplices, Computational Geometry: Theory and Applications 10 (1998), 71-76.


[116] An algorithm for finding many disjoint monochromatic edges in a complete 2-colored geometric graph (with G. Károlyi, G. Tardos, and G. Tóth), in: Intuitive Geometry (I. Bárány, K. Böröczky, eds.) Bolyai Society Mathematical Studies 6, Budapest, 1997, 367-372.


[117] On the number of incidences between points and curves (with M. Sharir), Combinatorics, Probability and Computing 7 (1998), 121-127.


[118] On the independence number of coin graphs (with G. Tóth), Geombinatorics 6 (1996), 30-33.


[119] Graphs drawn with few crossings per edge (with G. Tóth), in: Graph Drawing '96, Berkeley (S. North, ed.), Lecture Notes in Computer Science 1190, Springer-Verlag, Berlin, 1997, 345-354.
Also in: Combinatorica 17 (1997), 427-439.


[120] Geometric graphs and geometric hypergraphs, Graph Theory Notes of New York XXXI (1996), 39-43.


[121] Combinatorial geometry, in: Handbook of Discrete and Combinatorial Mathematics (K. H. Rosen, ed.), CRC Press, Boca Raton, 2000, 830-839.

[122] Two places at once (A remembrance of Paul Erdős), Mathematical Intelligencer 19(1997), Number 2, 38-48.
See also: Két helyen egyszerre (Emlékek Erdős Pálról), Világosság, December 1996, 70-79.


[123] Ramsey-type results for geometric graphs. II (with G. Károlyi, G. Tóth and P. Valtr), 13th ACM Symposium on Computational Geometry, Nice, ACM Press, 1997, 94-103.
Also in: Discrete and Computational Geometry 20 (1998), 375-388.


[124] Three-dimensional grid drawings of graphs (with T. Thiele and G. Tóth), in: Graph Drawing (Giuseppe DiBattista, ed.), Lecture Notes in Computer Science 1353, Springer-Verlag, Berlin, 1998, 47-51.
Also in: Advances in Discrete and Computational Geometry (B. Chazelle, J.E. Goodman and R. Pollack, eds.), Contemporary Mathematics 223, AMS, Providence, 1999, 251-255.


[125] Are there many distances that occur few times? (with P. Erdős), Geombinatorics 6 (1997), 77-78.

[126] On the boundary of the union of planar convex sets (with M. Sharir), Discrete and Computational Geometry 21 (1999), 321-328.


[127] Problem 75; Bemerkung zu Problem 75; Mathematische Semesterberichte 41 (1994), 208; 43 (1996).

[128] Problem 86: Covering with circles; Problem 88: Convex positions, Mathematische Semesterberichte 44 (1997), 93-94.

[129] A generalization of the Erdős-Szekeres theorem to disjoint convex sets (with G. Tóth), Discrete and Computational Geometry 19 (1998), 437-445.


[130] Canonical theorems for convex sets (with J. Solymosi), Discrete and Computational Geometry 19 (1998), 427-435.


[131] Folding and turning along geodesics in a convex surface, Geombinatorics 7 (1997), 61-65.


[132] Erdős-Szekeres-type theorems for segments and non-crossing convex sets (with G. Tóth), Geometriae Dedicata 81 (2000), 1-12.

[133] Halving lines and perfect cross-matchings (with J. Solymosi), in: Advances in Discrete and Computational Geometry (B. Chazelle, J.E. Goodman and R. Pollack, eds.), Contemporary Mathematics 223, AMS, Providence, 1999, 245-249.


[134] Which crossing number is it, anyway? (with G. Tóth), Proceedings of 39th Annual Symposium on Foundations of Computer Science, Palo Alto, 1998, 617-626.
Also in: Journal of Combinatorial Theory, Ser. B 80 (2000), 225-246.


[135] Popular distances in 3-space (with P. Erdős and G. Harcos), Discrete Mathematics 200 (1999), 95-99.


[136] New bounds on crossing numbers (with J. Spencer and G. Tóth), 15th ACM Symposium on Computational Geometry, 1999, 124-133.
Also in: Discrete and Computational Geometry 24 (2000), 623-644.


[137] Embedding planar graphs with fixed vertex locations (with R. Wenger), in: Graph Drawing '98 (Sue Whitesides, ed.), Lecture Notes in Computer Science 1547, Springer-Verlag, Berlin, 1998, 263-274.
Also in: Graphs and Combinatorics 17 (2001), 717-728.


[138] Crossroads in flatland, in:Combinatorics, Computation and Logic (C. S. Calude and M. J. Dinneen, eds.), Australian Computer Science Communications, Volume 21, Number 3, Springer Verlag, Singapore, 1999, 73-80.
Also in: MTA Közgyülési Előadások (J. Potó, ed.), Hungarian Academy of Sciences, Budapest, 1999, 131-138. (Title: Sík mezőben hármas út, in Hungarian.)

auckland.ps (english)
auckland.pdf (english)
sikmezo.ps (hungarian)
sikmezo.pdf (hungarian)

[139] Crossing numbers, in: Discrete and Computational Geometry (J. Akiyama et al, eds.), Lecture Notes in Computer Science 1763, Springer-Verlag, Berlin, 2000, 267-273.


[140] Geometric graph theory, in: Surveys in Combinatorics, 1999 (J. D. Lamb and D. A. Preece, eds.), London Mathemetical Society Lecture Notes 267, Cambridge University Press, Cambridge, 1999, 167-200.


[141] Cellular telephone networks and random maps in hypergraphs (with A. Halpert and F. Lengyel), Discrete Applied Mathematics 103 (2000), 111-126.


[142] Cutting glass (with G. Tardos), 16th ACM Symposium on Computational Geometry, 2000, 360-369.
Also in: Discrete and Computational Geometry 24 (2000), 481-495.


[143] Ramsey type theorems for tournaments and and for H-free graphs (with N. Alon and J. Solymosi), Combinatorica 21 (2001), 155-170.


[144] Radial points in the plane (with M. Sharir), European Journal of Combinatorics 22 (2001), 855-863.


[145] Bichromatic lines with few points (with R. Pinchasi), Journal of Combinatorial Theory, Ser. A 90 (2000), 326-335.


[146] Separating convex sets by straight lines (with G. Tardos), Discrete Mathematics 241 (2001), 427-433, special issue dedicated to the 65th birthday of Helge Tverberg.


[147] Thirteen problems on crossing numbers (with G. Tóth), Geombinatorics 9 (2000), 194-207.


[148] New results on the distribution of distances determined by a point set (with E. Makai and J. Spencer), Bolyai Society Mathematical Studies 11, Paul Erdős and his Mathematics, II, (G. Halász et al., eds.), Springer, Berlin etc., J. Bolyai Mathematical Society, Budapest, 2002, 499-511.


[149] Covering lattice points by subspaces (with I. Bárány, G. Harcos, and G. Tardos), Periodica Mathematica Hungarica 43 (2001), 93-103.



[150] On the boundary complexity of the union of fat triangles (with G. Tardos), Proceedings of 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, 2000, 423-431.
Also in: SIAM Journal of Computing 31 (2002), 1745-1760.

[151] Unavoidable configurations in complete topological graphs (with G. Tóth), in: Graph Drawing 2000, Lecture Notes in Computer Science 1984, Springer-Verlag, 2001, 328-337.
Also in: Discrete and Computational Geometry 30 (2003), 311-320.


[152] A Ramsey-type theorem for bipartite graphs (with P. Erdős and A. Hajnal), Geombinatorics 10 (2000), 64-68.


[153] The maximum number of times the same distance can occur among the vertices of a convex n-gon is O(nlogn) (with P. Braß), Journal of Combinatorial Theory, Ser. A 94 (2001), 178-179.


[154] A modular version of the Erdős-Szekeres theorem (with G. Károlyi and G. Tóth), Studia Sci. Math. Hung. 38 (2001), 245-259.


[155] On the number of balanced lines (with R. Pinchasi), Discrete and Computational Geometry 25 (2001), 611-628.


[156] Common tangents to four unit balls in R³ (with I. G. Macdonald and T. Theobald), Discrete and Computational Geometry 26 (2001), 1-17.


[157] Crossing patterns of segments (with J. Solymosi), Journal of Combinatorial Theory, Ser. A, 96 (2001), 316-325.


[158] The Happy End Problem - The beginning of combinatorial geometry (in Hungarian), in: New Mathematical Mosaic (A. Hraskó, ed.), Typotex, Budapest, 2002, 223-242.


[159] Structure theorems for systems of segments (with J. Solymosi), Discrete and Computational Geometry (J. Akiyama et al., eds), Lecture Notes in Computer Science 2098, Springer-Verlag, Berlin, 2001, 308-317.


[160]On the complexity of the union of geometric objects, Discrete and Computational Geometry (J. Akiyama et al., eds), Lecture Notes in Computer Science 2098, Springer-Verlag, Berlin, 2001, 292-307.


[161] The union of congruent cubes in three dimensions (with I. Safruti and M. Sharir), 17th ACM Symposium on Computational Geometry, ACM Press, 2001, 19-28.
Also in: Discrete and Computational Geometry 30 (2003), 133-160.


[162] Partitioning colored point sets into monochromatic parts (with A. Dumitrescu), in: WADS 2001, Workshop Algor. Data Struct., Lecture Notes in Computer Science 2125, Springer-Verlag, 2001, 264-275.
Also in: International J. Computational Geometry and Appl. 12 (2002), 401-412.


[163] Untangling a polygon (with G. Tardos), in: Graph Drawing 2001, Lecture Notes in Computer Science, Springer-Verlag, accepted.
Also in: Discrete and Computational Geometry 28 (2002), 585-592.


[164] Recognizing string graphs is decidable (with G. Tóth), in: Graph Drawing 2001, Lecture Notes in Computer Science 2265, Springer-Verlag, 247-260.
Also in: Discrete and Computational Geometry 28 (2002), 593-606.


[165] Lenses in arrangements of pseudo-circles and their applications (with P. K. Agarwal, E. Nevo, R. Pinchasi, M. Sharir, Sh. Smorodinsky), 18th ACM Symposium on Computational Geometry, ACM Press, New York, 2002, 123-132.
Also in: Journal of ACM 51 (2004), 139-186.


[166] How many unit equilateral triangles can be generated by n points in convex position? (with R. Pinchasi), American Mathematical Monthly 110 (2003), 400-406.


[167] The number of simplices embracing the origin (with M. Szegedy), in: Discrete Geometry: In honor of W. Kuperberg's 60th Birthday (A. Bezdek, ed.), Pure and Applied Mathematics, Marcel Dekker Inc., New York, 2003, 381-386.


[168] Isosceles triangles determined by a planar point set (with G. Tardos), Graphs and Combinatorics 18 (2002), 769-779.


[169] Geometric graphs with no self-intersecting path of length three (with R. Pinchasi, G. Tardos, and G. Tóth), in: Graph Drawing 2002, Lecture Notes in Computer Science 2528, Springer-Verlag, Berlin, 2002, 295-311.
Also in: European J. Combinatorics, 25 (2004), 793-811.


[170] Topological graphs with no large grids (with R. Pinchasi, M. Sharir, and G. Tóth), Graphs and Combinatorics 21 (2005), 355-364.



[171] Monotone drawings of planar graphs (with G. Tóth), in: Algorithms and Computation ( P. Bose, P. Morin, eds.) Lecture Notes in Computer Science 2518, Springer-Verlag, Berlin, 2002, 647-653.
Also in: Journal of Graph Theory, 46 (2004), 39-47.



[172] Geometric graph theory, in: Handbook of Discrete and Computational Geometry, 2nd edition, (J.E. Goodman and J. O'Rourke, eds.), CRC Press, Boca Raton, 2004, 219-238.

[173] Distinct distances in three and higher dimensions (with B. Aronov, M. Sharir, and G. Tardos), Thirty-Fifth Annual ACM Symposium on Theory of Computing (STOC 03), 541-546.
Also in: Combinatorics, Probability and Computing 13 (2004), 283-293.



[174] Conflict free colorings (with G. Tóth), in: Discrete and Computational Geometry - The Goodman-Pollack Festschrift (S. Basu et al, eds.), Springer Verlag, Berlin, 2003, 665-671.


[175] Relaxing planarity for topological graphs (with R. Radoičić and G. Tóth), in: Discrete and Computational Geometry (J. Akiyama, M. Kano, eds.), Lecture Notes in Computer Science 2866, Springer-Verlag, Berlin, 2003, 221-232.
Also in: Finite and Infinite Combinatorics (E. Győri and G. O. H. Katona, eds.), Bolyai Society Mathematical Studies 15, J. Bolyai Mathematical Society, Budapest, 2006, 285-300.



[176] How many ways can one draw a graph? (with G. Tóth), in: Graph Drawing (G. Liotta, ed.), Lecture Notes in Computer Science 2912, Springer-Verlag, Berlin, 2004, 47-58. Also in: Combinatorica 26 (2006), 559-576.


[177] A tight bound for the number of different directions in three dimensions (with R. Pinchasi and M. Sharir), 19th ACM Symposium on Computational Geometry, ACM Press, New York, 2003, 106-113. Also in: Journal of Combinatorial Theory, Ser. A 108 (2004), 1-16.



[178] Geometric Incidences (with M. Sharir), in: Towards a Theory of Geometric Graphs (J. Pach, ed.), Contemporary Mathematics, AMS, Providence, RI, 2004, 185-223.
Also in: Graph Theory, Combinatorics and Algorithms - Interdisciplinary Applications (M. Golumbic and I. Ben-Arroyo Hartman, eds.), Springer Verlag, New York, 2005, 267-292.



[179] Problem 19 (with G. Fejes Tóth and G. Tóth), in: Discrete Geometry (K. Bezdek. ed.), Marcel Dekker, Inc., New York, 2003, 454-455. Problem 365, Intersection graphs of convex sets, Discrete Mathematics 257 (2003), 602-603. Problem 367 (with G. Tóth), What is the true crossing number, Discrete Mathematics 257 (2003), 604-605.

[180] Midpoints of segments induced by a point set, Geombinatorics 13 (2003), 98-105.



[181] A generalization of quasi-planarity (with R. Radoičić and G. Tóth), in: Towards a Theory of Geometric Graphs (J. Pach, ed.), Contemporary Mathematics, AMS, Providence, RI, 2004, 177-183.



[182] Disjoint edges in topological graphs (with G. Tóth), in: Combinatorial Geometry and Graph Theory (J. Akiyama et al., eds.), Lecture Notes in Computer Science 3330, Springer-Verlag, Berlin, 2005, 133-140.



[183] Pushing squares around (with A. Dumitrescu), 20th ACM Symposium on Computational Geometry, ACM Press, New York, 2004, 116-123.
Also in: Graphs and Combinatorics 22 (2006), 37-50.



[184] Improving the Crossing Lemma by finding more crossings in sparse graphs (with R. Radoičić, G. Tardos, and G. Tóth), 20th ACM Symposium on Computational Geometry, ACM Press, New York, 2004, 68-75.
Also in: Discrete and Computational Geometry 36 (2006), 527-552.



[185] Solution of Scott's problem on the number of directions determined by a point set in 3-space (with R. Pinchasi and M. Sharir), 20th ACM Symposium on Computational Geometry, ACM Press, New York, 2004, 76-85.
Also in: Discrete and Computational Geometry 38 (2007), 399--441.



[186] Problems and results on geometric patterns (with P. Brass), in: Graph Theory and Combinatorial Optimization (D. Avis et al., eds.), Springer, 2005, 17-36.



[187] Forbidden paths and cycles in ordered graphs and matrices (with G. Tardos), Israel J. Math. 155 (2006), 309-334.



[188] Long alternating paths in bicolored point sets (with J. Kynčl and G. Tóth), in: Graph Drawing (J. Pach, ed.), Lecture Notes in Computer Science 3383, Springer-Verlag, Berlin, 2004, 340-348. Also in: Discrete Mathematics 308 (2008), 4315--4322.



[189] Crossing patterns of semi-algebraic sets (with N. Alon, R. Pinchasi, R. Radoičić, and M. Sharir), Journal of Combinatorial Theory Ser A 111 (2005), 310-326.



[190] Online conflict-free coloring for intervals (with A. Fiat, J. Matoušek, E. Mossel, M. Sharir, S. Smorodinsky, U. Wagner, and E. Welzl), ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), SIAM, Philadelphia, 2005, 545-554.
Also in: SIAM J. Computing 36 (2006), 1342-1359.



[191] A long noncrossing path among disjoint segments in the plane (with R. Pinchasi), in: Combinatorial and Computational Geometry, MSRI publications 52 (J.E. Goodman, J. Pach, E. Welzl, eds.), Cambridge University Press, 2005, 495-500.



[192] Nearly equal distances and Szemerédi's regularity lemma (with R. Radoičić and J. Vondrák), Computational Geometry: Theory and Appls. 34 (2006), 11-19.




[193] On the diameter of separated point sets with many nearly equal distances (with R. Radoičić and J. Vondrák), European J. Combinatorics 27 (2006), 1321-1332.



[194] Sliding disks in the plane (with S. Bereg and A. Dumitrescu), in: Discrete and Computational Geometry (JCDCG 2004) (J. Akiyama et al., eds.), Lecture Notes in Computer Science 3742, Springer-Verlag, Tokyo, 2005, 37-47.
Also in: International J. on Computational Geometry and Appl. 18 (2008), 373-387.



[195] The maximum number of empty congruent triangles determined by a point set (with G. Tóth and A. Dumitrescu), Revue Roumaine de Mathématiques Pures et Appliquées 50 (2005), 613-618.



[196] Crossing numbers of toroidal graphs (with G. Tóth), in: Graph Drawing 2005 (P. Healy et al., eds.), Lecture Notes in Computer Science 3843, Springer, Berlin, 2006, 334-342.
Also in: Topics in Discrete Mathematics (M. Klazar et al., eds), Algorithms and Combinatorics 26, Springer, Berlin, 2006, 581-590.



[197] The discrete charm of geometry (In memoriam László Fejes Tóth), Középiskolai Matematikai Lapok 2005/5.



[198] Directions in combinatorial geometry, Jahresbericht der Deutschen Mathematiker-Vereinigung 107 (2005), 215-225.



[199] Reconfigurations in graphs and grids (with G. Calinescu and A. Dumitrescu), Proc. LATIN '06 (Latin American Theoretical INformatics conference), Lecture Notes in Computer Science 3887, Springer, 2006, 262-273. Also in: SIAM J. Discrete Mathematics 22 (2008), 124--138.



[200] Degenerate crossing numbers (with G. Tóth), 22nd ACM Symposium on Computational Geometry, ACM Press, New York, 2006, 255-258.
Also in: Discrete and Computational Geometry 41 (2009), 376--384.



[201] Opposite-quadrant depth in the plane (with H. Brönnimann and J. Lenchner), Proc. 15th Ann. Fall Workshop on Computational Geometry. Also in: Graphs and Combinatorics 23 (2007), 145-152.


[202] Bounded-degree graphs can have arbitrarily large slope numbers (with D. Pálvölgyi), Electronic J. Combinatorics 13 (1) (2006), N1.



[203] Comments on Fox News (with G. Tóth), Geombinatorics 15 (2006), 150-154.



[204] On planar intersection graphs with forbidden subgraphs (with M. Sharir), J. Graph Theory 59 (2008), 205-214.



[205] Indecomposable coverings (with G. Tardos and G. Tóth), in: Discrete Geometry, Combinatorics and Graph Theory, The China--Japan Joint Conference (CJCDGCGT 2005), Lecture Notes in Computer Science 4381, Springer, 2007, 135-148. Also in: Canadian Mathematical Bulletin 52 (2009), no. 3, 451-463.



[206] Drawing cubic graphs with at most five slopes parameter (with B. Keszegh, D. Pálvölgyi, and G. Tóth), Graph Drawing 2006, Lecture Notes in Computer Science 4372, Springer, 2007, 114-125. Also in: Computational Geometry: Theory and Applications 40 (2008), 138-147.



[207] Planar crossing numbers of graphs embeddable in another surface (with K. Böröczky and G. Tóth), Internat. J. of Foundations of Comp. Science, 17 (2006), 1005-1011.



[208] A bipartite analogue of Dilworth's theorem for multiple partial orders (with J. Fox), European J. Combinatorics 30 (2009), 1846-1853.



[209] Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles (with X. Chen, M. Szegedy, and G. Tardos), Symp. on Discrete Algorithms (SODA 2008), ACM, New York–SIAM, Philadelphia, 2008, 94-101. Also in: Random Structures and Algorithms 34 (2009), 11-23.



[210] Decomposition of multiple coverings into many parts (with G. Tóth), 23rd ACM Symposium on Computational Geometry, ACM Press, New York, 2007, 133-137. Also in: Discrete and Computational Geometry 42 (2009), 127-133.



[211] On regular vertices of the union of planar objects (with E. Ezra and M. Sharir), 23rd ACM Symposium on Computational Geometry, ACM Press, New York, 2007, 220-226. Also in: Discrete and Computational Geometry 41 (2009), 216-231.



[212] Separator theorem and Turán-type results for planar intersection graphs (with J. Fox), Advances in Mathematics 219 (2008), 1070-1080.



[213] Turán-type results for partial orders and intersection graphs of convex sets (with J. Fox and Cs. D. Tóth), Israel J. Math. 178 (2010), 29-50.



[214] Erdos--Hajnal-type results on intersection patterns of geometric objects (with J. Fox), in: Horizons of Combinatorics (E. Győri, ed.), Bolyai Soc. Math. Studies 17, J. Bolyai Mathematical Soc., Budapest, 2008, 79-103.



[215] Intersection patterns of curves (with J. Fox and Cs. D. Tóth), J. London Math. Soc., accepted.



[216] Points surrounding the origin (with A. Holmsen and H. Tverberg), Combinatorica 28 (2008), 633-634.



[217] A bipartite strengthening of the Crossing Lemma (with J. Fox and Cs. D. Tóth), in: Graph Drawing (S.-H. Hong, T. Nishizeki, eds.), Lecture Notes in Computer Science 4875, Springer-Verlag, Berlin, 2008, 13-24. Also in J. Combinat. Theory Ser. B 100 (2010), 23-35.



[218] Coloring axis-parallel rectangles (with G. Tardos), Computational Geometry and Graph Theory (KyotoCGGT2007), Lecture Notes in Computer Science, Vol. 4535, Springer-Verlag, Berlin, 2008, 178-185. Also in: J. of Combinatorial Theory Ser. A, accepted.



[219] Coloring K_k-free intersection graphs of geometric objects in the plane (with J. Fox), SoCG 2008, ACM Press, New York, 2008, 346-354. Also in: European J. Combinatorics, to appear.



[220] Families of convex sets not representable by points (with G. Tóth), in: Indian Statistical Institute Platinum Jubilee Commemorative Volume--Architecture and Algorithms (B. B. Bhattacharya et al., eds.), World Scientific, Singapore, 2009, 43-53.



[221] State of the Union--of Geometric Objects (with P.K. Agarwal and M. Sharir), Surveys in Discrete and Computational Geometry Twenty Years Later (J. E. Goodman et al., eds.), Contemporary Mathematics, AMS, Providence, RI, vol. 453, AMS, Providence, RI, 2008, 9-48.



[222] Crossing numbers of imbalanced graphs (with J. Solymosi and G. Tardos), J. Graph Theory, accepted.



[223] Intersecting convex sets by rays (with R. Fulek and A. Holmsen), in: Proceedings 24th annual Symposium on Computational Geometry, ACM Press, 2008, 385-391. Also in: Discrete and Computational Geometry 42 (2009), 343-358.



[224] Convexly independent subsets of the Minkowski sum of planar point sets (with F. Eisenbrand, T. Rothvoss, and N. Sopher), Electronic J. of Combinatorics 15 (2008), N8.



[225] Monochromatic empty triangles in two-colored point sets (with G. Tóth), in: Geometry, Games, Graphs and Education: the Joe Malkevitch Festschrift (S. Garfunkel, R. Nath, eds.), COMAP, Bedford, MA, 2008, 195-198. Also in: Discrete Applied Mathematics 161 (2013), 1259-1261.

[226] Conflict-free colorings of graphs and hypergraphs (with G. Tardos), Combinatorics, Probability and Computing 18 (2009), 819-834.



[227] On grids in topological graphs (with E. Ackerman, J. Fox, and A. Suk), in: Proceedings 24th annual Symposium on Computational Geometry, ACM Press, 2009, 403-412.



[228] Cubic graphs have bounded slope parameter (with B. Keszegh, D. Pálvölgyi, and G. Toth), in: Graph Drawing 2008 (I. G. Tollis and M. Patrignani, eds.), Lecture Notes in Computer Science 5417, Springer-Verlag, Berlin, 2009, 50-60. Also in: J. Graph Algorithms and Applications 14 (2010), 5-17.



[229] Combinatorial Geometry and its Algorithmic Applications: The Alcala Lectures (with M. Sharir), Mathematical Surveys and Monographs, Vol. 152, AMS, Providence, 2009.



[230] A separator theorem for string graphs and its applications (with J. Fox). In: WALCOM: Algorithms and Computation, Lecture Notes in Computer Science 5431, Springer-Verlag, Berlin, 2009, 1-14. Also in: Combinatorics, Probability and Computing 19 (2010), 371-390.



[231] Drawing Hamiltonian cycles with no large angles (with A. Dumitrescu and G. Tóth), Graph Drawing 2009, Lecture Notes in Computer Science 5849, Springer-Verlag, Berlin, 2010, 3-14. Also in: Electronic J. of Combinatorics 19 (2012), Issue 2, P31.



[232] Minimum clique partition in unit disk graphs (with A. Dumitrescu), Graphs and Combinatorics 27 (2011), 399-411.



[233] A computational approach to Conway's thrackle conjecture (with R. Fulek). in: Graph Drawing 2010, Lecture Notes in Computer Science 6502, Springer-Verlag, Berlin, 2011, 226-237. Also in: Computat. Geom.: Theory and Appls. 44 (2011), 345-355.



[234] String graphs and incomparability graphs (with J. Fox), in: Proceedings 28th Annual Symposium on Computational Geometry (Chapel Hill, NC), ACM Press, New York, 2012, 405-414. Also in: Advances in Mathematics 230 (2012), 1381-1401.



[235] A note on blocking visibility between points (with A. Dumitrescu and G. Tóth), Geombinatorics, 19(1), 2009, 67-73.



[236] Crossings between curves with many tangencies (with J. Fox, F. Frati, and R. Pinchasi), in: Proc. WALCOM: Workshop on Algorithms and Computation, Lecture Notes in Computer Science 5942, Springer-Verlag, 2010, 1-8. Also in: An Irregular Mind (I. Bárány, L. Solymosi, eds.), Bolyai Society Mathematical Studies, Vol. 21, 2010, 251-260.



[237] Conway's conjecture for monotone thrackles (with E. Sterling), American Mathematical Monthly 118, June/July 2011, 544-548.



[238] On the structure of graphs with low obstacle number (with D. Sarioz), Graphs and Combinatorics 27 (2011), 465-473.



[239] Graphs with large obstacle numbers (with P. Mukkamala, D. Sarioz), Proc. WG 2010: 36th Intern. Workshop on Graph Theoretic Concepts in Computer Science, Lecture Notes in Computer Science 6410, Springer-Verlag, Berlin, 2010, 292-303.



[240] Overlap properties of geometric expanders (with J. Fox, M. Gromov, V. Lafforgue, A. Naor), Proc. 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), San Francisco, California, 2011, 1188-1197. Also in: Journal fur die reine und angewandte Mathematik (Crelle) 671 (2012), 49-83.



[241] Drawing planar graphs of bounded degree with few slopes (with B. Keszegh and D. Pálvölgyi), in: Graph Drawing 2010, Lecture Notes in Computer Science 6502, Springer-Verlag, 2011, 293-304. Also in: SIAM J. Discrete Math. 27 (2013), no. 2, 1171-1183.



[242] Opaque sets (with A. Dumitrescu and M. Jiang), in: Approximation, Randomization, and Combinatorial Optimization (APPROX 2011), Lecture Notes in Computer Science Volume 6845 (2011), 194-205. Also in: Algorithmica, accepted.



[243] Remarks on a Ramsey theory for trees (with J. Solymosi and G. Tardos), Combinatorica 32 (2012), 473-482.



[244] Computing the independence number of intersection graphs (with J. Fox), Proc. 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), San Francisco, California, 1161-1165.



[245] On the queue-number of planar graphs (with G. Di Battista, F. Frati), in: Proc. 51st Annual IEEE Symposium on Foundations of Computer Science, (FOCS 2010), Las Vegas, Nevada, 2010, 365-374. Also: SIAM J. Computing, accepted.



[246] Tangencies between families of disjoint regions in the plane (with A. Suk and M. Treml), in: Proc. 26th Annual Symposium on Computational Geometry, Snowbird, Utah, 2010, 423-428. Also in: Computational Geometry: Theory and Appls. 45 (2012), 131-138.



[247] Tight lower bounds for the size of epsilon-nets (with G. Tardos), in: Proc. 27th Annual Symposium on Computational Geometry (SoCG 2011), Paris, France, 2011, 458-463. Also in: J. American Mathematical Society 26 (2013), no. 3, 645-658.



[248] Lower bounds on the obstacle number of graphs (with P. Mukkamala, D. Pálvölgyi), Electronic J. Combin. 19 (2012), P32.



[249] Monotone crossing number (with G. Tóth), in: Graph Drawing 2011, Lecture Notes in Computer Science 7034, Springer-Verlag, Berlin, 2011, 278-289. Also in: Moscow Journal of Combinatorics and Number Theory 2 (2012), 216-231.



[250] Disjoint homometric sets in graphs (with M. O. Albertson, M. E. Young), Ars Math. Contemp. 4 (2011), 1-4.



[251] "Square trisection": Dissection of a square in three congruent partitions (with Ch. Blanvillain), Bull. d'Informatique Approfondie et Appls. 86 (2010), 7-17.



[252] Erdős-Szekeres-type theorems for monotone paths and convex bodies (with J. Fox, B. Sudakov, A. Suk), Proceedings of the London Mathematical Society 105 (2012), 953--982.



[253] Piercing quasi-rectangles - On a problem of Danzer and Rogers (with G. Tardos), Journal of Combinatorial Theory Ser. A 119 (2012), 1391-1397.



[254] Every graph admits an unambiguous bold drawing, in: Graph Drawing 2011 (M. van Kreveld, B. Speckmann, eds.), Lecture Notes in Computer Science 7034, Springer-Verlag, Berlin, 2011, 332-342. Also in Journal of Graph Algorithms and Applications 19 (2015), 299-312.



[255] Homogeneous selections from hyperplanes (with I. Bárány), Journal of Combinatorial Theory Ser. B 104 (2014), 81-87.



[256] Large simplices determined by finite point sets (with F. Morić), Beiträge für Algebra und Geometrie 54 (2013), 45-57.



[257] The number of edges of k-quasi-planar graphs (with J. Fox, A. Suk), SIAM J. Discrete Mathematics 27 (2013), 550-561.



[258] Tangled thrackles (with R. Radoičić and G. Tóth), Geombinatorics 21 (2012), 157-169. Also in: Proc. XIV Spanish Meeting on Computational Geometry, EGC 2011 (Dedicated to Ferran Hurtado), Lecture Notes in Computer Science 7579, Springer-Verlag, Berlin, 2012, 45-53.



[259] How many potatoes are in a mesh? (with M. van Kreveld and M. Löffler), in: Proc. 28th European Workshop on Computational Geometry (EuroCG 2012), Assisi, Italy, 2012, 277-280. Also in: Proc. 23rd International Symposium on Algorithms and Computation (ISAAC 2012), Lecture Notes in Computer Science 7676, Springer-Verlag, Berlin, 2012, 166-176.



[260] Survey on decomposition of multiple coverings (with G. Tóth and D. Pálvölgyi), in: Geometry - Intuitive, Discrete, and Convex (I. Bárány, K. J. Böröczky et al., eds.), Bolyai Society Mathematical Studies, Vol. 24, Springer-Verlag, Berlin, 2013, 219--257.



[261] The visible perimeter of an arrangement of disks (with G. Nivasch, G. Tardos), in: Graph Drawing 2012, Lecture Notes in Computer Science 7704, Springer-Verlag, Berlin, 2013, 364-375. Also in: Computational Geometry: Theory and Appls. 47 (2014), 42-51.



[262] The number of distinct distances from a vertex of a convex polygon (with G. Nivasch, R. Pinchasi, Sh. Zerbib), J. Computational Geometry 4 (2013), 1-12.



[263] A note on coloring line arrangements (with E. Ackerman, R.Pinchasi, R. Radoičić, G. Tóth), Electronic J. Combinatorics 21 (2014), no. 2, Paper 2.23.



[264] On Schur's conjecture (with F. Morić), in: Thailand-Japan Joint Conference on Computational Geometry and Graphs (TJJCCGG12), Lecture Notes in Computer Science 8296, Springer-Verlag, Berlin, 120-131, 2013. Also in: Comput. Geom.: Theory and Appls 48 (2015), no. 7, 520-527.



[265] The range of a random walk on a comb (with G. Tardos), Electronic J. Combinatorics 20 (2013), p. 59.



[266] Ramsey-type results for semi-algebraic relations (with D. Conlon, J. Fox, B. Sudakov, A. Suk), in: Proc. 29th Annual ACM Symposium on Computational Geometry (SoCG 2013), ACM Press, New York, 2013, 309-318. Also in: Trans. Amer. Math. Soc. 366 (2014), no. 9, 5043-5065.



[267] The Erdős-Hajnal conjecture for rainbow triangles (with J. Fox, A. Grinshpun), Journal of Combinatorial Theory, Ser B 111 (2015), 75-125.



[268] The beginnings of geometric graph theory, in: Erdős Centennial (L. Lovász et al., eds.), Bolyai Society Mathematical Studies 25, Springer-Verlag, Berlin, 2013, 465-484.



[269] Applications of a new separator theorem (with J. Fox), Combinatorics, Probability and Computing 23 (2014), 66-74.



[270] Two and a half billion years of distance research (with F. Morić), Geombinatorics XXII (2013), Issue 4, 182-191.



[271] On the upward planarity of mixed plane graphs (with F. Frati, M. Kaufmann, C. D. Tóth, D. R. Wood), in: Graph Drawing 2013, Lecture Notes in Computer Science 8242, Springer-Verlag, Berlin, 2013, 1–12. Also in: Journal of Graph Algorithms and Applications 18, no. 2 (2014), 253-279.



[272] Saturated simple topological graphs (with R. Radoičić and G. Tóth), Computational Geometry: Theory and Appls. 48 (2015), 295-310.



[273] Distinct distances on algebraic curves in the plane (with F. de Zeeuw), Proc. 30th Annual Symposium on Computational Geometry (SoCG 2014), ACM Press, New York, 2014, 549-557.



[274] Cross-intersecting sets of vectors (with G. Tardos), Discrete and Computational Geometry and Graphs, Lecture Notes in Computer Science, Springer-Verlag 8845 (J. Akiyama. H. Ito, T. Sakai, eds.), Springer, 2014, 122-137. Also in: Graphs Combin. 31 (2015), no. 2, 477-495.



[275] Weight balancing on boundaries and skeletons (with L. Barba, J. De Carufel, O. Cheong, M. Dobbins, R. Fleischer, A. Kawamura, M. Korman, Y. Okamoto, Y. Tang, T. Tokuyama, S. Verdonschot, T. Wang), Proc. 30th Annual Symposium on Computational Geometry (SoCG 2014), ACM Press, New York, 2014, 436-443.



[276] Decomposition of multiple packings with subquadratic union complexity (with B. Walczak), Combinatorics, Probability and Computing 25 (2016), no. 1, 145-153.



[277] A precise threshold for quasi-Ramsey numbers (with R. J. Kang, V. Patel, G. Regts), SIAM J. Discrete Mathematics 29 (2015), no. 3, 1670-1682.



[278] A lower bound on opaque sets (with A. Kawamura, S. Moriyama, Y. Otachi), in: Proc. 32nd Annual Symposium on Computational Geometry (SoCG 2016), LIPIcs 51 (2016), 46:1-10. Also: Computational Geometry: Theory and Appls. 80 (2019), 13-22.



[279] Double-normal pairs in space (with K. Swanepoel), Mathematika 61 (2015), no. 1, 259-272.



[280] Double-normal pairs in the plane and on the sphere (with K. Swanepoel), Beitr. Algebra Geom. 56 (2015), no. 2, 423-438.



[281] Geometric intersection patterns and the theory of geometric graphs, in: Proceedings of the International Congress of Mathematicians 2014 (ICM 2014, Seoul, South Korea), 455-474.



[282] A semi-algebraic version of Zarankiewicz's problem (with J. Fox, A. Sheffer, A. Suk, J. Zahl), J. European Math. Society 19 (2017), 1785-1810.



[283] Density and regularity theorems for semi-algebraic hypergraphs (with J. Fox and A. Suk), in Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015, San Diego), SIAM, 2015, 1517-1530. Another version: A polynomial regularity lemma for semi-algebraic hypergraphs and its applications in geometry and property testing, SIAM J. Computing 45 (2016), no. 6, 2199-2223.



[284] Unsplittable coverings in the plane (with D. Pálvölgyi), in: Mayr E. (eds) Graph--Theoretic Concepts in Computer Science. WG 2015. Lecture Notes in Computer Science, vol 9224. Springer, Berlin, 2015, 281-296. Also in: Advances in Mathematics 302 (2016), 433-457.



[285] On the Richter-Thomassen conjecture about pairwise intersecting closed curves (with N. Rubin and G. Tardos), in: Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015, San Diego), SIAM, 2015, 1506-1515. Also in: Combinatorics, Probability and Computing 25 (2016), no. 6, 941-958.



[286] Note on k-planar crossing numbers (with L. A. Székely, C. D. Tóth, G. Tóth), Computational Geometry: Theory and Applications 68 (2018), 2-6.



[287] Translative covering of the space with slabs (with A. Kupavskii), Amer. Math. Monthly 124, No. 6, June-July (2017), 483-493.



[288] Semi-algebraic colorings of complete graphs (with J. Fox and A. Suk), manuscript.



[289] Beyond the Richter-Thomassen conjecture (with N. Rubin and G. Tardos), in: Proc. 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016, Arlington), SIAM, 2016, 957-968. Also: A crossing lemma for Jordan curves, Advances in Mathematics 331 (2018), 908--940.



[290] On the Zarankiewicz problem for intersection hypergraphs (with N. Mustafa), in: Graph Drawing 2015, Lecture Notes in Computer Science 9411, Springer-Verlag, Berlin, 2015, 207-216. Also in: Journal of Combinatorial Theory Ser. A 141 (2016), 1-7.



[291] New lower-bounds for epsilon-nets (with A. Kupavskii, N. Mustafa), in: Proc. 32nd Annual Symposium on Computational Geometry (SoCG 2016), LIPIcs 51 (2016), 54:1-16. Almost the same as: Near-optimal lower bounds for epsilon-nets for half-spaces and low complexity set systems, in: A Journey Through Discrete Mathematics (M. Loebl et al., eds.), Springer, Cham, 2017, 527--541.



[292] Separation with restricted families of sets (with Z. Lángi, M. Naszódi, G. Tardos, G. Tóth), J. Combinatorial Theory Ser. A 144 (2016), 292-305.



[293] Borsuk and Ramsey type questions in Euclidean space (with P. Frankl, C. Reiher, and V. Rödl), in: Connections in Discrete Mathematics - A celebration of the work of Ron Graham, Cambridge Univ. Press, Cambridge, 2018, 259-277.



[294] Decomposition of a cube into nearly equal smaller cubes (with P. Frankl, A. Meir), American Mathematical Monthly 124, No. 10 (2017), 895-904.



[295] Simultaneous approximation of polynomials (with A. Kupavskii), in: Discrete and Computational Geometry and Graphs (JCDCGG 2015, J. Akiyama et al., eds.), Lecture Notes in Computer Science 9943, Springer-Verlag, Berlin, 2016, 193-203.



[296] Sphere-of-influence graphs in normed spaces (with M. Naszódi, K. Swanepoel), in: Discrete Geometry and Symmetry (M. Conder et al., eds.), Springer Proc. Math. Stat., 234, Springer, Cham, 2018, 293-296.



[297] More distinct distances under local conditions (with J. Fox, A. Suk), Combinatorica 38 (2018), No. 2, 501-509.



[298] Approximating the rectilinear crossing number (with J. Fox and A. Suk), in: Graph Drawing 2016 (Y. Hu and M. Nöllenburg, eds.), Lecture Notes in Computer Science 9801, 413-426, 2016.



[299] Arrangements of homothets of a convex body (with M. Naszódi, K. Swanepoel), Mathematika 63 (2017), no. 2, 696-710.



[300] Graphs with no grid obstacle representation, Geombinatorics, XXVI (2) (2016), 80-83.



[301] Beyond the Magic Mountain (A Varázshegyen túl, in Hungarian), Érintő (Elektronikus Mat. Lapok), September 2016 and Élet \és Irodalom, August 12, 2016.



[302] On the size of k-cross-free families (with A. Kupavskii and I. Tomon), Combinatorica 39(1) (2019): 153-164.



[303] Controlling Lipschitz functions (with A. Kupavskii and G. Tardos), Mathematika 64 (2018), 898-910.



[304] Disjointness graphs of segments (with G. Tardos and G. Tóth), in: Proc. 33rd Annual Symposium on Computational Geometry (SoCG 2017), 59:1-15. Combin. Probab. Computing 30 (2021), no. 4, 498-512.



[305] Erdős-Hajnal conjecture for graphs with bounded VC-dimension (with J. Fox and A. Suk), in: Proc. 33rd Annual Symposium on Computational Geometry (SoCG 2017), 43:1-15. Also in: Discret. Comput. Geom. 61(4) (2019), 809-829.



[306] Many touchings force many crossings (with G. Tóth), in: 25th Internat. Symposium on Graph Drawing (GD2017). Lecture Notes in Computer Science 10692, Springer, 2018, 153-169. Also in: J. Comb. Theory, Ser. B 137 (2019), 104-111.



[307] Thrackles: An improved upper bound (with R. Fulek), in: 25th Internat. Symposium on Graph Drawing (GD2017). Lecture Notes in Computer Science 10692, Springer, 2018, 153-169. Also in: Discret. Appl. Math. 259 (2019), 226-231.



[308] Two extensions of the Erdős-Szekeres problem (with A. Holmsen, H. Nassajian Mojarrad, G. Tardos), J. European Math. Soc. 22 (2020), no. 12, 3981-3995.





[309] Tilings with noncongruent triangles (with A. Kupavskii and G. Tardos), European J. Combin. 73 (2018), 72-80.

wp/td>


[310] Tilings of the plane with unit area triangles of bounded diameter (with A. Kupavskii and G. Tardos), Acta Math. Hung. 155 (2018), no. 1, 175-183.



[311] A crossing lemma for multigraphs (with G. Tóth), in: Proc. 34th Annual Symposium on Computational Geometry (SoCG 2018), 65:1-13, 2018. Also in: Discret. Comput. Geom. 63(4) (2020): 918-933.



[312] Almost all string graphs are intersection graphs of plane convex sets (with B. Reed, Y. Yuditsky), in: Proc. 34th Annual Symposium on Computational Geometry (SoCG 2018), 68:1-14, 2018. Also in: Discret. Comput. Geom. 63(4) (2020): 888-917.



[313] A note on the clique chromatic number of geometric graphs (with J. Fox, A. Suk), Geombinatorics XXVIII (2018), Issue 2, 83-92.



[314] Tiling the plane with equilateral triangles (with G. Tardos), Geombinatorics, Geombinatorics XXVIII (2019), no. 4, 197-205.



[315] Ramsey-Turán numbers for semi-algebraic graphs (with J. Fox and A. Suk), Electron. J. Comb. 25(4): P4.61 (2018).



[316] A stability theorem for cube tessellations (with P. Frankl), Computational Geometry 9 (2018), no. 1, 387-390.



[317] Planar point sets determine many pairwise crossing segments (with N. Rubin and G. Tardos), STOC 2019: 1158-1166. Also in: Advances in Mathematics 386 (2021), 107779. (On-line)



[318] On the chromatic number of disjointness graphs of curves (with I. Tomon), Proc. 35th Annual Symposium on Computational Geometry (SoCG 2019), 54:1-17, LIPIcs, 2019. Also in: J. Combinatorial Theory B, 144 (2020): 167-190.



[319] The number of crossings in multigraphs with no empty lens (with M. Kaufmann, G. Toth, and T. Ueckerdt), in: Graph Drawing and Network Visualization, Lecture Notes in Comput. Sci. 11282, Springer, Cham, 2018, 242-254. Also in: J. Graph Algorithms and Applications 25 (2021), 383-396.



[320] Ordered graphs and large bi-cliques in intersection graphs of curves (with I. Tomon), European J. Combinatorics 82 (2019), 102994 (on-line). (Extended abstract in: Acta Math. Univ. Comenian. (N.S.) 88 (2019), no. 3, 985-988.)



[321] Large homogeneous submatrices (with D. Korándi and I. Tomon), SIAM J. Discrete Mathematics 34(4) (2020): 2532-2552.



[322] Green-Wins Solitaire revisited--Simultaneous flips that affect many edges (with M. Hoffmann and M. Stojaković), in: 35th European Workshop on Computational Geometry 2019, 9:1-6.



[323] Small triangular containers for triangles--On a problem of Nandakumar (with G. Kiss), Mathematics Newsletter-Ramanujan Mathematical Society 30 (2019), no. 3, 69-71.



[324] Coloring Hasse diagrams and disjointness graphs of curves (with I. Tomon), in: Graph Drawing and Network Visualization '19, Lecture Notes in Comput. Sci. 11904, Springer-Verlag, Cham, 2019, 244-250.



[325] Colorings with only rainbow arithmetic progressions (with I. Tomon), Acta Mathematica Hungarica 161 (2020): 507-515.



[326] Bounded VC-dimension implies the Schur-Erdős conjecture (with J. Fox and A. Suk), in: Proc. 36th Annual Symposium on Computational Geometry (SoCG 2020), 46:1-46:8. Also in: Combinatorica 41 (6) (2021), 803-813.



[327] Erdős-Hajnal-type results for ordered paths (with I. Tomon), J. Combinat. Theory Ser. B 151 (2021), 21-37.



[328] Shattered matchings in intersecting hypergraphs (with P. Frankl), Moscow Journal of Combinatorics and Number Theory 10(1) (2021), 49-59.



[329] Crossings between non-homotopic edges (with G. Tardos and G. Tóth), in: Graph Drawing and Network Visualization '20, Lecture Notes in Comput. Sci. 12590, Springer-Verlag, Cham, 2020, 359-371. Best paper award. Also in: J. Comb. Theory, Ser. B 156 (2022), 389-404.



[330] Minimum area isosceles containers (with G. Kiss and G. Somlai), Journal of Information Processing 28 (2020), 759-765.



[331] Sunflowers in set systems of bounded dimension (with J. Fox and A. Suk), in: 37th Symp. Computational Geometry (SoCG 2021), 37:1-37:13. Also in: Comb. 43 (1) (2023), 187-202.



[332] On well-connected sets of strings (with P. Frankl), Electronic J. Combinatorics, Electron. J. Comb. 29 (1) (2022).



[333] Exchange properties of finite set-systems (with D. Pálvölgyi and P. Frankl), in: Extended Abstracts EuroComb 2021 (J. Ne\v set\v ril et al, eds.), Springer, 2021. Also in: SIAM J. Discrete Mathematics 36 (2022), no. 3, 2073-2081.



[334] On the number of edges of separated multigraphs (with J. Fox and A. Suk), in: Graph Drawing and Network Visualization '21, accepted. Lecture Notes in Computer Science, vol. 12868, 223-227, Springer, 2021. Also in: J. Graph Theory, accepted.



[335] Disjointness graphs of short polygonal chains (with G. Tardos and G. Tóth), 38th Symp. on Computational Geometry (SoCG 2022), 56:1-56:12.



[336] Quasiplanar graphs, string graphs, and the Erdős-Gallai problem (with J. Fox and A. Suk), in: 30th International Symposium on Graph Drawing and Network Visualization (GD 2022), Lecture Notes in Computer Science, vol. 13764. Springer, Cham, 219-231. Also in: European J. Combinatorics, accepted.



[337] Random necklaces require fewer cuts (with N. Alon, D. Elboim, and G. Tardos), submitted.



[338] Optimal embedded and enclosing isosceles triangles (with A. Ambrus, M. Csikós, G. Kiss, and G. Somlai), International Journal of Foundations of Computer Science 34 (7) (2023), 737-760.



[339] Successive vertex orderings of fully regular graphs (with L. Fang, H. Huang, G. Tardos, J. Zuo), J. Comb. Theory, Ser. A 199 (2023): 105776 (online).



[340] Where have all the grasshoppers gone? (with G. Tardos). Amer. Math. Monthly, accepted.



[341] Odd-sunflowers (with P. Frankl and D. Pálvölgyi), Eurocomb 2023, accepted.



[342] Monochromatic configurations on a circle (with G. Damásdi, N. Frankl, and D. Pálvölgyi), Eurocomb 2023, accepted.



[344] Maximum Betti numbers of \v Cech complexes (with H. Edelsbrunner), in: 40th Annual Symposium on Computational Geometry (SoCG 2024), submitted.



[345] A structure theorem for intersection graphs of pseudo-segments and its applications (with J. Fox and A. Suk), in: 40th Annual Symposium on Computational Geometry (SoCG 2024), submitted.



Here is a another list of my publications, compiled by MathSciNet.