TY - GEN

T1 - Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles

AU - Chen, Xiaomin

AU - Pach, János

AU - Szegedy, Mario

AU - Tardos, Gábor

PY - 2008

Y1 - 2008

N2 - Given a point set P in the plane, the Delaunay graph with respect to axis-parallel rectangles is a graph defined on the vertex set P, whose two points p,q ∈ P are connected by an edge if and only if there is a rectangle parallel to the coordinate axes that contains p and q, but no other elements of P. The following question of Even et al. [ELRS03] was motivated by a frequency assignment problem in cellular telephone networks. Does there exist a constant c > 0 such that the Delaunay graph of any set of n points in general position in the plane contains an independent set of size at least cn? We answer this question in the negative, by proving that the largest independent set in a randomly and uniformly selected point set in the unit square is O(n log 2 log n/log n), with probability tending to 1. We also show that our bound is not far from optimal, as the Delaunay graph of a uniform random set of n points almost surely has an independent set of size at least cn/log n. We give two further applications of our methods. 1. We construct 2-dimensional n-element partially ordered sets such that the size of the largest independent sets of vertices in their Hasse diagrams is o(n). This answers a question of Matoušek and Přívětivý [MaP06] and improves a result of Kříž and Nešetřil [KrN91]. 2. For any positive integers c and d, we prove the existence of a planar point set with the property that no matter how we color its elements by c colors, we find an axis-parallel rectangle containing at least d points, all of which have the same color. This solves an old problem from [BrMP05].

AB - Given a point set P in the plane, the Delaunay graph with respect to axis-parallel rectangles is a graph defined on the vertex set P, whose two points p,q ∈ P are connected by an edge if and only if there is a rectangle parallel to the coordinate axes that contains p and q, but no other elements of P. The following question of Even et al. [ELRS03] was motivated by a frequency assignment problem in cellular telephone networks. Does there exist a constant c > 0 such that the Delaunay graph of any set of n points in general position in the plane contains an independent set of size at least cn? We answer this question in the negative, by proving that the largest independent set in a randomly and uniformly selected point set in the unit square is O(n log 2 log n/log n), with probability tending to 1. We also show that our bound is not far from optimal, as the Delaunay graph of a uniform random set of n points almost surely has an independent set of size at least cn/log n. We give two further applications of our methods. 1. We construct 2-dimensional n-element partially ordered sets such that the size of the largest independent sets of vertices in their Hasse diagrams is o(n). This answers a question of Matoušek and Přívětivý [MaP06] and improves a result of Kříž and Nešetřil [KrN91]. 2. For any positive integers c and d, we prove the existence of a planar point set with the property that no matter how we color its elements by c colors, we find an axis-parallel rectangle containing at least d points, all of which have the same color. This solves an old problem from [BrMP05].

UR - http://www.scopus.com/inward/record.url?scp=78650421910&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78650421910&partnerID=8YFLogxK

M3 - Conference contribution

SN - 9780898716474

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 94

EP - 101

BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -