Empty region graphs

DOI10.1016/j.comgeo.2008.09.003zbMath1161.05314OpenAlexW2133911915MaRDI QIDQ1000919

Stefan Langerman, Jean Cardinal, Sébastien Collette

Publication date: 12 February 2009

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2008.09.003

zbMATH Keywords

connectivityplanaritygeometric graphsgraph propertiesskeletonsbipartitenessbounded degreeproximity graphsneighbourhoodmonotone propertiesconditions that ensure properties desirable in applicationsconstructing a graph from a point setcycle-freenessempty regions graphsERGnearest neighbour graphstight regionstriangle-freeness

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75)

Related Items

Local properties of geometric graphs, Measuring the Error in Approximating the Sub-Level Set Topology of Sampled Scalar Data, On a family of strong geometric spanners that admit local routing strategies, Sigma-local graphs, A survey of neighborhood construction algorithms for clustering and classifying data points

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The relative neighborhood graph for mixed feature variables
• Classes of graphs which approximate the complete Euclidean graph
• The \(\gamma\)-neighborhood graph
• Relative neighborhood graphs in three dimensions
• On nearest-neighbor graphs
• Characterizing proximity trees
• On the Spanning Ratio of Gabriel Graphs and beta-Skeletons
• On the Inequality of Cover and Hart in Nearest Neighbor Discrimination
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Every monotone graph property has a sharp threshold