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

DOI10.1002/rsa.20246zbMath1228.05226OpenAlexW2514202683MaRDI 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 coloringVoronoi diagramsfrequency assignmentHasse diagramDelauney graphs

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (18)

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

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

This page was built for publication: Delaunay graphs of point sets in the plane with respect to axis‐parallel rectangles