48 citations · 165 across the 65 of their papers we have counts for
67 papers · 1 filter
Cutting a convex body into fat parts and approximating Euclidean distance by graph distances
János Pach, Gábor Tardos
Can one construct a graph on the set of integer points in the plane such that the length of the shortest path between any two vertices of differs from their…
Countable Graphs with Finite Path-width: Characterisation and Universality
Tony Huynh, Freddie Illingworth, Nikolai Karol +4
We study path-width and the closely related parameter line-width in countably infinite graphs. Our first result characterises the graphs of finite path-width: they are the graphs t…
On traces of randomly rolling polytopes
Kenneth Moore, János Pach
Let be a three-dimensional convex polytope resting with one of its faces on the plane. At each step, is allowed to roll over a randomly selected edge of…
How large part of a graph can be covered by the neighborhoods of k vertices?
Janos Pach
Let be fixed integer, a constant. Consider a graph with vertices and average degree . We answer a question of Simon Griffiths by showing that has $…
Is the space of reachable particle configurations dense?
Janos Pach, Gabor Tardos
Let be a finite sequence of points in an Euclidean space . Suppose that there is a (pointlike) particle sitting at each point . In a ``legal'' move, any…
A structure theorem for pseudo-segments and its applications
Jacob Fox, Janos Pach, Andrew Suk
We prove a far-reaching strengthening of Szemerédi's regularity lemma for intersection graphs of pseudo-segments. It shows that the vertex set of such a graph can be partitioned in…