TY - JOUR
T1 - Witness (Delaunay) graphs
AU - Aronov, Boris
AU - Dulieu, Muriel
AU - Hurtado, Ferran
N1 - Funding Information:
E-mail address: [email protected] (F. Hurtado). 1 Research partially supported by a grant from the U.S.–Israel Binational Science Foundation and NSF Grant CCF-08-30691. Research by B.A. also partially supported by NSA MSP Grant H98230-06-1-0016. 2 Partially supported by projects MEC MTM2006-01267, MTM2009-07242, Gen. Catalunya DGR 2005SGR00692 and 2009SGR1040.
PY - 2011/8
Y1 - 2011/8
N2 - Proximity graphs are used in several areas in which a neighborliness relationship for input data sets is a useful tool in their analysis, and have also received substantial attention from the graph drawing community, as they are a natural way of implicitly representing graphs. However, as a tool for graph representation, proximity graphs have some limitations that may be overcome with suitable generalizations. We introduce a generalization, witness graphs, that encompasses both the goal of more power and flexibility for graph drawing issues and a wider spectrum for neighborhood analysis. We study in detail two concrete examples, both related to Delaunay graphs, and consider as well some problems on stabbing geometric objects and point set discrimination, that can be naturally described in terms of witness graphs.
AB - Proximity graphs are used in several areas in which a neighborliness relationship for input data sets is a useful tool in their analysis, and have also received substantial attention from the graph drawing community, as they are a natural way of implicitly representing graphs. However, as a tool for graph representation, proximity graphs have some limitations that may be overcome with suitable generalizations. We introduce a generalization, witness graphs, that encompasses both the goal of more power and flexibility for graph drawing issues and a wider spectrum for neighborhood analysis. We study in detail two concrete examples, both related to Delaunay graphs, and consider as well some problems on stabbing geometric objects and point set discrimination, that can be naturally described in terms of witness graphs.
KW - Delaunay graph
KW - Graph drawing
KW - Proximity graphs
KW - Witness graphs
UR - http://www.scopus.com/inward/record.url?scp=79851512356&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79851512356&partnerID=8YFLogxK
U2 - 10.1016/j.comgeo.2011.01.001
DO - 10.1016/j.comgeo.2011.01.001
M3 - Article
AN - SCOPUS:79851512356
SN - 0925-7721
VL - 44
SP - 329
EP - 344
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
IS - 6-7
ER -