Delaunay graphs of point sets in the plane with respect to axis‐parallel rectangles
From MaRDI portal
Publication:3608310
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
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