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

DOI10.1002/rsa.20246zbMath1228.05226MaRDI QIDQ3608310

Xiaomin Chen, Mario Szegedy, János Pach, Gábor Tardos

Publication date: 4 March 2009

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: http://infoscience.epfl.ch/record/129408

zbMATH Keywords

graph coloring; Voronoi diagrams; frequency assignment; Hasse diagram; Delauney graphs

Mathematics Subject Classification ID

52B55: Computational aspects related to convexity

68R10: Graph theory (including graph drawing) in computer science

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

05C15: Coloring of graphs and hypergraphs

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Tight lower bounds for the size of epsilon-nets, Hitting and Piercing Rectangles Induced by a Point Set, Improved Ramsey-type results for comparability graphs, Hasse diagrams with large chromatic number, Coloring Hypergraphs Defined by Stabbed Pseudo-Disks and ABAB-Free Hypergraphs, Coloring Axis-Parallel Rectangles, Matching random colored points with rectangles, Polychromatic colorings of unions of geometric hypergraphs, Colouring bottomless rectangles and arborescences, Conflict-free coloring for rectangle ranges using \(O(n ^{.382})\) colors, On variants of conflict-free-coloring for hypergraphs, Witness rectangle graphs, Coloring axis-parallel rectangles, Coloring points with respect to squares, Coloring Delaunay-edges and their generalizations, Dushnik-Miller dimension of TD-Delaunay complexes, Proper coloring of geometric hypergraphs

Cites Work

• Conflict-free coloring for rectangle ranges using \(O(n ^{.382})\) colors
• Coloring axis-parallel rectangles
• Covering the plane with convex polygons
• Computational geometry algorithms for the systolic screen
• Chromatic number of Hasse diagrams, eyebrows and dimension
• Conflict-free coloring of points and simple regions in the plane
• Research Problems in Discrete Geometry
• On The Chromatic Number of Geometric Hypergraphs
• CONFLICT-FREE COLORINGS OF SHALLOW DISCS
• On rectangular visibility
• Fast algorithms for direct enclosures and direct dominances
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• On the independence number of sparse graphs
• Online Conflict‐Free Coloring for Intervals
• Conflict-Free Colorings of Rectangles Ranges
• Indecomposable Coverings