Witness Gabriel graphs

Boris Aronov; Muriel Dulieu; Ferran Hurtado

doi:10.1016/j.comgeo.2011.06.004

Witness Gabriel graphs

Boris Aronov, Muriel Dulieu, Ferran Hurtado

Research output: Contribution to journal › Article › peer-review

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	https://doi.org/10.1016/j.comgeo.2011.06.004
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

Access to Document

10.1016/j.comgeo.2011.06.004

Cite this

@article{5fcb568370b64f8bae4b917feec8b78f,

title = "Witness Gabriel graphs",

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.",

keywords = "Gabriel graph, Graph drawing, Proximity graph, Witness graph",

author = "Boris Aronov and Muriel Dulieu and Ferran Hurtado",

note = "Funding Information: Part of this research was done while the third author was visiting Polytechnic, supported by Grant AGAUR-Generalitat de Catalunya 2007 BE-1 00033 . ",

year = "2013",

doi = "10.1016/j.comgeo.2011.06.004",

language = "English (US)",

volume = "46",

pages = "894--908",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier B.V.",

number = "7",

}

TY - JOUR

T1 - Witness Gabriel graphs

AU - Aronov, Boris

AU - Dulieu, Muriel

AU - Hurtado, Ferran

N1 - Funding Information: Part of this research was done while the third author was visiting Polytechnic, supported by Grant AGAUR-Generalitat de Catalunya 2007 BE-1 00033 .

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Gabriel graph

KW - Graph drawing

KW - Proximity graph

KW - Witness graph

UR - http://www.scopus.com/inward/record.url?scp=84878535127&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84878535127&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2011.06.004

DO - 10.1016/j.comgeo.2011.06.004

M3 - Article

AN - SCOPUS:84878535127

SN - 0925-7721

VL - 46

SP - 894

EP - 908

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 7

ER -

Witness Gabriel graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this