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)

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

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)