### Abstract

We consider a generalization of the Gabriel graph, the witness Gabriel graph. Given a set of vertices P and a set of witness points 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.

Original language | English (US) |
---|---|

Pages (from-to) | 894-908 |

Number of pages | 15 |

Journal | Computational Geometry: Theory and Applications |

Volume | 46 |

Issue number | 7 |

DOIs | |

State | Published - 2013 |

### Keywords

- Gabriel graph
- Graph drawing
- Proximity graph
- Witness graph

### ASJC Scopus subject areas

- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics

## Fingerprint Dive into the research topics of 'Witness Gabriel graphs'. Together they form a unique fingerprint.

## Cite this

Aronov, B., Dulieu, M., & Hurtado, F. (2013). Witness Gabriel graphs.

*Computational Geometry: Theory and Applications*,*46*(7), 894-908. https://doi.org/10.1016/j.comgeo.2011.06.004