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

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