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

DOI10.1002/RSA.20246MaRDI QIDQ3608310zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• Coloring Delaunay-edges and their generalizations
• On coloring points with respect to rectangles
• Some geometric applications of Dilworth's theorem
• scientific article; zbMATH DE number 866009
• Coloring Axis-Parallel Rectangles

Cites work

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

Cited in

(24)

• Improved Ramsey-type results for comparability graphs
• Coloring hypergraphs defined by stabbed pseudo-disks and \(ABAB\)-free hypergraphs
• Dushnik-Miller dimension of stair contact complexes
• Hasse diagrams with large chromatic number
• Colouring bottomless rectangles and arborescences
• Stabbing boxes with finitely many axis-parallel lines and flats
• Dushnik-Miller dimension of TD-Delaunay complexes
• Coloring lines and Delaunay graphs with respect to boxes
• Proper coloring of geometric hypergraphs
• Coloring Delaunay-edges and their generalizations
• Coloring Axis-Parallel Rectangles
• Conflict-free coloring for rectangle ranges using \(O(n ^{.382})\) colors
• Witness rectangle graphs
• Nice point sets can have nasty Delaunay triangulations
• Polychromatic colorings of unions of geometric hypergraphs
• Coloring axis-parallel rectangles
• On variants of conflict-free-coloring for hypergraphs
• Coloring points with respect to squares
• Coloring hypergraphs defined by stabbed pseudo-disks and ABAB-free hypergraphs
• Tight lower bounds for the size of epsilon-nets
• Matching random colored points with rectangles
• Hitting and Piercing Rectangles Induced by a Point Set
• Word-representable graphs: orientations, posets, and bounds
• scientific article; zbMATH DE number 5764872 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3608310)