Witness Gabriel graphs

DOI10.1016/J.COMGEO.2011.06.004MaRDI QIDQ359756zbMATH OpenOpenAlexFDO

Authors Boris Aronov, Muriel Dulieu, Ferran Hurtado

Publication date 22 August 2013

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.1051, http://www.sciencedirect.com/science/article/pii/S0925772111000496

zbMATH Keywords

graph drawingGabriel graphproximity graphwitness Gabriel graphwitness graph

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: We consider a generalization of the Gabriel graph, the witness Gabriel graph. Given a set of vertices P and a set of witnesses W in the plane, there is an edge ab between two points of P in the witness Gabriel graph GG-(P,W) if and only if the closed disk with diameter ab does not contain any witness point (besides possibly a and/or b). We study several properties of the witness Gabriel graph, both as a proximity graph and as a new tool in graph drawing.

Recommendations

• Witness (Delaunay) graphs
• Mutual witness proximity graphs
• Witness rectangle graphs
• Witness rectangle graphs
• On locally Gabriel geometric graphs

Cites work

• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
• Approximate proximity drawings
• Constructing Arrangements of Lines and Hyperplanes with Applications
• GEOMETRIC PROXIMITY GRAPHS FOR IMPROVING NEAREST NEIGHBOR METHODS IN INSTANCE-BASED LEARNING AND DATA MINING
• The strength of weak proximity
• Witness (Delaunay) graphs
• Witness rectangle graphs

Cited in

(15)

• Matchings in higher-order Gabriel graphs
• Characterizing proximity trees
• Witness rectangle graphs
• Efficient Computation of Elliptic Gabriel Graph
• On the union complexity of diametral disks
• Approximate proximity drawings
• Witness rectangle graphs
• The Mathematics of Ferran Hurtado: A Brief Survey
• Mutual witness proximity graphs
• On locally Gabriel geometric graphs
• Hitting and Piercing Rectangles Induced by a Point Set
• Higher-order triangular-distance Delaunay graphs: graph-theoretical properties
• Mutual witness Gabriel drawings of complete bipartite graphs
• Witness (Delaunay) graphs
• Mutual witness Gabriel drawings of complete bipartite graphs

This page was built for publication: Witness Gabriel graphs

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