48 citations · 165 across the 65 of their papers we have counts for
4 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 $…