János Pach

According to our database1, János Pach authored at least 248 papers between 1980 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of one.

Awards

ACM Fellow

ACM Fellow 2011, "For contributions to computational geometry.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
On the chromatic number of disjointness graphs of curves.
J. Comb. Theory, Ser. B, 2020

A Crossing Lemma for Multigraphs.
Discret. Comput. Geom., 2020

Almost All String Graphs are Intersection Graphs of Plane Convex Sets.
Discret. Comput. Geom., 2020

Bounded VC-Dimension Implies the Schur-Erdős Conjecture.
Proceedings of the 36th International Symposium on Computational Geometry, 2020

2019
Many touchings force many crossings.
J. Comb. Theory, Ser. B, 2019

Ordered graphs and large bi-cliques in intersection graphs of curves.
Eur. J. Comb., 2019

Erdős-Hajnal Conjecture for Graphs with Bounded VC-Dimension.
Discret. Comput. Geom., 2019

Thrackles: An improved upper bound.
Discret. Appl. Math., 2019

Beyond-Planar Graphs: Combinatorics, Models and Algorithms (Dagstuhl Seminar 19092).
Dagstuhl Reports, 2019

A lower bound on opaque sets.
Comput. Geom., 2019

Approximating the rectilinear crossing number.
Comput. Geom., 2019

On the Size of K-Cross-Free Families.
Combinatorica, 2019

Planar point sets determine many pairwise crossing segments.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Coloring Hasse Diagrams and Disjointness Graphs of Curves.
Proceedings of the Graph Drawing and Network Visualization - 27th International Symposium, 2019

Semi-Algebraic Colorings of Complete Graphs.
Proceedings of the 35th International Symposium on Computational Geometry, 2019

2018
A stability theorem on cube tessellations.
JoCG, 2018

Tilings with noncongruent triangles.
Eur. J. Comb., 2018

Note on k-planar crossing numbers.
Comput. Geom., 2018

Ramsey-Turán Numbers for Semi-Algebraic Graphs.
Electr. J. Comb., 2018

More Distinct Distances Under Local Conditions.
Combinatorica, 2018

The Number of Crossings in Multigraphs with No Empty Lens.
Proceedings of the Graph Drawing and Network Visualization - 26th International Symposium, 2018

2017
Distinct Distances on Algebraic Curves in the Plane.
Comb. Probab. Comput., 2017

Tilings of the plane with unit area triangles of bounded diameter.
CoRR, 2017

A Crossing Lemma for Jordan Curves.
CoRR, 2017

Controlling Lipschitz functions.
CoRR, 2017

Disjointness Graphs of Segments.
Proceedings of the 33rd International Symposium on Computational Geometry, 2017

2016
A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing.
SIAM J. Comput., 2016

On the Zarankiewicz problem for intersection hypergraphs.
J. Comb. Theory, Ser. A, 2016

Separation with restricted families of sets.
J. Comb. Theory, Ser. A, 2016

Thirtieth Anniversary Note from the Editors in Chief.
Discret. Comput. Geom., 2016

Guest Editors' Foreword.
Discret. Comput. Geom., 2016

Beyond-Planar Graphs: Algorithmics and Combinatorics (Dagstuhl Seminar 16452).
Dagstuhl Reports, 2016

Decomposition of Multiple Packings with Subquadratic Union Complexity.
Comb. Probab. Comput., 2016

On the Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves.
Comb. Probab. Comput., 2016

Beyond the Richter-Thomassen Conjecture.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

New Lower Bounds for epsilon-Nets.
Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015
A Precise Threshold for Quasi-Ramsey Numbers.
SIAM J. Discret. Math., 2015

Every graph admits an unambiguous bold drawing.
J. Graph Algorithms Appl., 2015

The Erdős-Hajnal conjecture for rainbow triangles.
J. Comb. Theory, Ser. B, 2015

Cross-Intersecting Families of Vectors.
Graphs Comb., 2015

From Tarski's plank problem to simultaneous approximation.
CoRR, 2015

A polynomial regularity lemma for semi-algebraic hypergraphs and its applications in geometry and property testing.
CoRR, 2015

Remarks on Schur's conjecture.
Comput. Geom., 2015

Saturated simple and k-simple topological graphs.
Comput. Geom., 2015

Unsplittable Coverings in the Plane.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2015

Density and regularity theorems for semi-algebraic hypergraphs.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Simultaneous Approximation of Polynomials.
Proceedings of the Discrete and Computational Geometry and Graphs - 18th Japan Conference, 2015

2014
On the Upward Planarity of Mixed Plane Graphs.
J. Graph Algorithms Appl., 2014

Homogeneous selections from hyperplanes.
J. Comb. Theory, Ser. B, 2014

Applications of a New Separator Theorem for String Graphs.
Comb. Probab. Comput., 2014

The visible perimeter of an arrangement of disks.
Comput. Geom., 2014

On grids in topological graphs.
Comput. Geom., 2014

A Note on Coloring Line Arrangements.
Electr. J. Comb., 2014

Opaque Sets.
Algorithmica, 2014

Weight Balancing on Boundaries and Skeletons.
Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

2013
Drawing Planar Graphs of Bounded Degree with Few Slopes.
SIAM J. Discret. Math., 2013

The Number of Edges in k-Quasi-planar Graphs.
SIAM J. Discret. Math., 2013

On the Queue Number of Planar Graphs.
SIAM J. Comput., 2013

The number of distinct distances from a vertex of a convex polygon.
JoCG, 2013

On Schur's conjecture.
Electron. Notes Discret. Math., 2013

Monochromatic empty triangles in two-colored point sets.
Discret. Appl. Math., 2013

The Range of a Random Walk on a Comb.
Electr. J. Comb., 2013

Ramsey-type results for semi-algebraic relations.
Proceedings of the Symposuim on Computational Geometry 2013, 2013

A Remark on Transversal Numbers.
Proceedings of the Mathematics of Paul Erdős I, 2013

2012
Piercing quasi-rectangles - On a problem of Danzer and Rogers.
J. Comb. Theory, Ser. A, 2012

Coloring Kk-free intersection graphs of geometric objects in the plane.
Eur. J. Comb., 2012

Tangencies between families of disjoint regions in the plane.
Comput. Geom., 2012

Lower Bounds on the Obstacle Number of Graphs.
Electr. J. Comb., 2012

Drawing Hamiltonian Cycles with no Large Angles.
Electr. J. Comb., 2012

Remarks on a Ramsey theory for trees.
Combinatorica, 2012

How Many Potatoes Are in a Mesh?
Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

String graphs and incomparability graphs.
Proceedings of the Symposuim on Computational Geometry 2012, 2012

2011
Conway's Conjecture for Monotone Thrackles.
Am. Math. Mon., 2011

Intersection patterns of curves.
J. Lond. Math. Soc., 2011

On the Structure of Graphs with Low Obstacle Number.
Graphs Comb., 2011

Minimum Clique Partition in Unit Disk Graphs.
Graphs Comb., 2011

Letter from the New Editors-in-Chief.
Discret. Comput. Geom., 2011

A computational approach to Conway's thrackle conjecture.
Comput. Geom., 2011

Disjoint homometric sets in graphs.
Ars Math. Contemp., 2011

Computing the Independence Number of Intersection Graphs.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Overlap properties of geometric expanders.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Tangled Thrackles.
Proceedings of the Computational Geometry - XIV Spanish Meeting on Computational Geometry, 2011

Monotone Crossing Number.
Proceedings of the Graph Drawing - 19th International Symposium, 2011

Tight lower bounds for the size of epsilon-nets.
Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

2010
Crossing numbers of imbalanced graphs.
Journal of Graph Theory, 2010

Cubic graphs have bounded slope parameter.
J. Graph Algorithms Appl., 2010

Coloring axis-parallel rectangles.
J. Comb. Theory, Ser. A, 2010

A bipartite strengthening of the Crossing Lemma.
J. Comb. Theory, Ser. B, 2010

A Separator Theorem for String Graphs and its Applications.
Comb. Probab. Comput., 2010

Small (2,s)-colorable graphs without 1-obstacle representations
CoRR, 2010

Opaque sets
CoRR, 2010

"square trisection". dissection of a square in three congruent partitions.
BIAA, 2010

Graphs with Large Obstacle Numbers.
Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

Crossings between Curves with Many Tangencies.
Proceedings of the WALCOM: Algorithms and Computation, 4th International Workshop, 2010

2009
Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles.
Random Struct. Algorithms, 2009

A bipartite analogue of Dilworth's theorem for multiple partial orders.
Eur. J. Comb., 2009

Degenerate Crossing Numbers.
Discret. Comput. Geom., 2009

Intersecting Convex Sets by Rays.
Discret. Comput. Geom., 2009

On Regular Vertices of the Union of Planar Convex Objects.
Discret. Comput. Geom., 2009

Conflict-Free Colourings of Graphs and Hypergraphs.
Comb. Probab. Comput., 2009

Decomposition of multiple coverings into many parts.
Comput. Geom., 2009

Why Are String Graphs So Beautiful?
Proceedings of the Graph Drawing, 17th International Symposium, 2009

2008
Reconfigurations in Graphs and Grids.
SIAM J. Discret. Math., 2008

On planar intersection graphs with forbidden subgraphs.
Journal of Graph Theory, 2008

Sliding Disks in the Plane.
Int. J. Comput. Geom. Appl., 2008

On Simplices Embracing a Point.
Electron. Notes Discret. Math., 2008

Long alternating paths in bicolored point sets.
Discret. Math., 2008

Guest Editors' Foreword.
Discret. Math., 2008

Foreword.
Discret. Comput. Geom., 2008

Drawing cubic graphs with at most five slopes.
Comput. Geom., 2008

Convexly Independent Subsets of the Minkowski Sum of Planar Point Sets.
Electr. J. Comb., 2008

Points surrounding the origin.
Combinatorica, 2008

Coloring kk-free intersection graphs of geometric objects in the plane.
Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

2007
Online Conflict-Free Coloring for Intervals.
SIAM J. Comput., 2007

Opposite-Quadrant Depth in the Plane.
Graphs Comb., 2007

Solution of Scott's Problem on the Number of Directions Determined by a Point Set in 3-Space.
Discret. Comput. Geom., 2007

Foreword.
Discret. Comput. Geom., 2007

Guest Editors' Foreword.
Algorithmica, 2007

On regular vertices on the union of planar objects.
Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, 2007

2006
Planar Crossing Numbers of Graphs Embeddable in Another Surface.
Int. J. Found. Comput. Sci., 2006

Pushing Squares Around.
Graphs Comb., 2006

On the diameter of separated point sets with many nearly equal distances.
Eur. J. Comb., 2006

Improving the Crossing Lemma by Finding More Crossings in Sparse Graphs.
Discret. Comput. Geom., 2006

Nearly equal distances and Szemerédi's regularity lemma.
Comput. Geom., 2006

Bounded-Degree Graphs can have Arbitrarily Large Slope Numbers.
Electr. J. Comb., 2006

How Many Ways Can One Draw A Graph?
Combinatorica, 2006

2005
Guest Editor's Foreword.
J. Graph Algorithms Appl., 2005

Crossing patterns of semi-algebraic sets.
J. Comb. Theory, Ser. A, 2005

Topological Graphs with No Large Grids.
Graphs Comb., 2005

Online conflict-free coloring for intervals.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Crossing Number of Toroidal Graphs.
Proceedings of the Graph Drawing, 13th International Symposium, 2005

Forbidden patterns and unit distances.
Proceedings of the 21st ACM Symposium on Computational Geometry, 2005

Indecomposable Coverings.
Proceedings of the Discrete Geometry, 2005

Research problems in discrete geometry.
Springer, 2005

2004
Geometric Graph Theory.
Proceedings of the Handbook of Discrete and Computational Geometry, Second Edition., 2004

Finite Point Configurations.
Proceedings of the Handbook of Discrete and Computational Geometry, Second Edition., 2004

Monotone drawings of planar graphs.
Journal of Graph Theory, 2004

On the number of directions determined by a three-dimensional points set.
J. Comb. Theory, Ser. A, 2004

Lenses in arrangements of pseudo-circles and their applications.
J. ACM, 2004

Geometric graphs with no self-intersecting path of length three.
Eur. J. Comb., 2004

Distinct Distances in Three and Higher Dimensions.
Comb. Probab. Comput., 2004

Improving the crossing lemma by finding more crossings in sparse graphs: [extended abstract].
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

2003
How Many Unit Equilateral Triangles Can Be Generated by N Points in Convex Position?
Am. Math. Mon., 2003

Unavoidable Configurations in Complete Topological Graphs.
Discret. Comput. Geom., 2003

The Union of Congruent Cubes in Three Dimensions.
Discret. Comput. Geom., 2003

Disjoint Edges in Topological Graphs.
Proceedings of the Combinatorial Geometry and Graph Theory, 2003

A tight bound for the number of different directions in three dimensions.
Proceedings of the 19th ACM Symposium on Computational Geometry, 2003

2002
On the Boundary Complexity of the Union of Fat Triangles.
SIAM J. Comput., 2002

Covering lattice points by subspaces.
Period. Math. Hung., 2002

Partitioning Colored Point Sets into Monochromatic Parts.
Int. J. Comput. Geom. Appl., 2002

Isosceles Triangles Determined by a Planar Point Set.
Graphs Comb., 2002

Recognizing String Graphs Is Decidable.
Discret. Comput. Geom., 2002

Untangling a Polygon.
Discret. Comput. Geom., 2002

Relaxing Planarity for Topological Graphs.
Proceedings of the Discrete and Computational Geometry, Japanese Conference, 2002

Lenses in arrangements of pseudo-circles and their applications.
Proceedings of the 18th Annual Symposium on Computational Geometry, Barcelona, 2002

2001
Crossing Patterns of Segments.
J. Comb. Theory, Ser. A, 2001

The Maximum Number of Times the Same Distance Can Occur among the Vertices of a Convex n-gon Is O(n log n).
J. Comb. Theory, Ser. A, 2001

Embedding Planar Graphs at Fixed Vertex Locations.
Graphs Comb., 2001

Radial Points in the Plane.
Eur. J. Comb., 2001

Separating convex sets by straight lines.
Discret. Math., 2001

On the Number of Balanced Lines.
Discret. Comput. Geom., 2001

Common Tangents to Four Unit Balls in R3.
Discret. Comput. Geom., 2001

Ramsey-type Theorems with Forbidden Subgraphs.
Combinatorica, 2001

2000
Which Crossing Number Is It Anyway?
J. Comb. Theory, Ser. B, 2000

Bichromatic Lines with Few Points.
J. Comb. Theory, Ser. A, 2000

Cutting Glass.
Discret. Comput. Geom., 2000

New Bounds on Crossing Numbers.
Discret. Comput. Geom., 2000

Cellular telephone networks and random maps in hypergraphs.
Discret. Appl. Math., 2000

Structure Theorems for Systems of Segments.
Proceedings of the Discrete and Computational Geometry, Japanese Conference, 2000

On the Complexity of the Union of Geometric Objects.
Proceedings of the Discrete and Computational Geometry, Japanese Conference, 2000

Unavoidable Configurations in Complete Topological Graphs.
Proceedings of the Graph Drawing, 8th International Symposium, 2000

1999
Discrete And Computational Geometry.
Proceedings of the Handbook of Discrete and Combinatorial Mathematics., 1999

Popular distances in 3-space.
Discret. Math., 1999

On the Boundary of the Union of Planar Convex Sets.
Discret. Comput. Geom., 1999

Uniformly Distributed Distances - a Geometric Application of Janson's Inequality.
Combinatorica, 1999

1998
A Generalization of the Erdos - Szekeres Theorem to Disjoint Convex Sets.
Discret. Comput. Geom., 1998

Canonical Theorems for Convex Sets.
Discret. Comput. Geom., 1998

Guest Editor's Foreword.
Discret. Comput. Geom., 1998

Ramsey-Type Results for Geometric Graphs, II.
Discret. Comput. Geom., 1998

Extremal Problems for Geometric Hypergraphs.
Discret. Comput. Geom., 1998

On the Number of Incidences Between Points and Curves.
Comb. Probab. Comput., 1998

On circumscribing polygons for line segments.
Comput. Geom., 1998

A Tverberg-type result on multicolored simplices.
Comput. Geom., 1998

Crossing Numbers.
Proceedings of the Discrete and Computational Geometry, Japanese Conference, 1998

1997
On Conway's Thrackle Conjecture.
Discret. Comput. Geom., 1997

Ramsey-Type Results for Geometric Graphs, I.
Discret. Comput. Geom., 1997

Graphs Drawn with Few Crossings per Edge.
Combinatorica, 1997

Quasi-Planar Graphs Have a Linear Number of Edges.
Combinatorica, 1997

Three-dimensional Grid Drawings of Graphs.
Proceedings of the Graph Drawing, 5th International Symposium, 1997

1996
Applications of the Crossing Number.
Algorithmica, 1996

Ramsey-Type Results for Geometric Graphs.
Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

1995
A Left-First Search Algorithm for Planar Graphs.
Discret. Comput. Geom., 1995

Guest Editor's Forword.
Discret. Comput. Geom., 1995

Combinatorial geometry.
Wiley-Interscience series in discrete mathematics and optimization, Wiley, ISBN: 978-0-471-58890-0, 1995

1994
Fat Triangles Determine Linearly Many Holes.
SIAM J. Comput., 1994

Some Geometric Applications of Dilworth's Theorem.
Discret. Comput. Geom., 1994

The Complexity of a Class of Infinite Graphs.
Combinatorica, 1994

Crossing Families.
Combinatorica, 1994

1993
Extremal problems in graph drawings (abstract).
SIGACT News, 1993

The grid revisted.
Discret. Math., 1993

How Hard Is Half-Space Range Searching.
Discret. Comput. Geom., 1993

An Invariant Property of Balls in Arrangements of Hyperplanes.
Discret. Comput. Geom., 1993

Nearly Equal Distances in the Plane.
Comb. Probab. Comput., 1993

Weaving Patterns of Lines and Line Segments in Space.
Algorithmica, 1993

1992
Arrangements of Curves in the Plane - Topology, Combinatorics and Algorithms.
Theor. Comput. Sci., 1992

Repeated Angles in the Plane and Related Problems.
J. Comb. Theory, Ser. A, 1992

A turán-type theorem on chords of a convex polygon.
J. Comb. Theory, Ser. B, 1992

An Upper Bound on the Number of Planar K-Sets.
Discret. Comput. Geom., 1992

Almost Tight Bounds for epsilon-Nets.
Discret. Comput. Geom., 1992

On the Number of Convex Lattice Polygons.
Comb. Probab. Comput., 1992

1991
On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm.
SIAM J. Comput., 1991

On the maximal number of certain subgraphs inKr-free graphs.
Graphs Comb., 1991

On the Average Volume of Subsets in Euclidean d-Space.
Eur. J. Comb., 1991

Universal elements and the complexity of certain classes of infinite graphs.
Discret. Math., 1991

Distinct Distances Determined By Subsets of a Point Set in Space.
Comput. Geom., 1991

Fat Triangles Determine Linearly Many Holes
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Layout of Rooted Trees.
Proceedings of the Planar Graphs, 1991

1990
Note on vertex-partitions of infinite graphs.
Discret. Math., 1990

Special issue dedicated to discrete and computational geometry.
Combinatorica, 1990

How to draw a planar graph on a grid.
Combinatorica, 1990

Variation on the theme of repeated distances.
Combinatorica, 1990

Weaving Patterns of Lines and Segments in Space.
Proceedings of the Algorithms, 1990

Notes on Geometric Graph Theory.
Proceedings of the Discrete and Computational Geometry: Papers from the DIMACS Special Year, 1990

Gaps in Difference Sets, and the Graph of Nearly Equal Distances.
Proceedings of the Applied Geometry And Discrete Mathematics, 1990

On the Perimeter of a Point Set in the Plane.
Proceedings of the Discrete and Computational Geometry: Papers from the DIMACS Special Year, 1990

Some New Bounds for Epsilon-Nets.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

The Combinatorial Complexity of Hyperplane Transversals.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

1989
Radius, diameter, and minimum degree.
J. Comb. Theory, Ser. B, 1989

The Upper Envelope of Piecewise Linear Functions and the Boundary of a Region Enclosed by Convex Plates: Combinatorial Analysis.
Discret. Comput. Geom., 1989

On Arrangement of Jordan Arcs with Three Intersection per Pair.
Discret. Comput. Geom., 1989

1988
Explicit codes with low covering radius.
IEEE Trans. Inf. Theory, 1988

An extremal problem on Kr-free graphs.
Journal of Graph Theory, 1988

Cutting a graph into two dissimilar halves.
Journal of Graph Theory, 1988

How to make a graph bipartite.
J. Comb. Theory, Ser. B, 1988

Repeated distances in space.
Graphs Comb., 1988

Small Sets Supporting Fáry Embeddings of Planar Graphs
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

On Arrangements of Jordan Arcs with Three Intersections per Pair.
Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

1987
Bounding one-way differences.
Graphs Comb., 1987

On the Lower Envelope of Bivariate Functions and its Applications
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

1986
Maximal volume enclosed by plates and proof of the chessboard conjecture.
Discret. Math., 1986

Covering the Plane with Convex Polygons.
Discret. Comput. Geom., 1986

On the Union of Jordan Regions and Collision-Free Translational Motion Amidst Polygonal Obstacles.
Discret. Comput. Geom., 1986

1984
On disjointly representable sets.
Combinatorica, 1984

1983
On a Quasi-Ramsey problem.
Journal of Graph Theory, 1983

On the Number of Sets in a Null t-Design.
Eur. J. Comb., 1983

1981
A Problem of Ulam on Planar Graphs.
Eur. J. Comb., 1981

Graphs whose every independent set has a common neighbour.
Discret. Math., 1981

1980
On a problem of L. Fejes Tóth.
Discret. Math., 1980


  Loading...