CHARACTERIZING PROXIMITY TREES

Authors
BOSE P LENHART W LIOTTA G
Citation
P. Bose et al., CHARACTERIZING PROXIMITY TREES, Algorithmica, 16(1), 1996, pp. 83-110
Citations number
27
Categorie Soggetti
Computer Sciences",Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Algorithmica → ACNP
ISSN journal
01784617
Volume
16
Issue
1
Year of publication
1996
Pages
83 - 110
Database
ISI
SICI code
0178-4617(1996)16:1<83:CPT>2.0.ZU;2-U
Abstract
Complete characterizations are given for those trees that can be drawn as either the relative neighborhood graph, relatively closest graph, Gabriel graph, or modified Gabriel graph of a set of points in the pla ne. The characterizations give rise to linear-time algorithms for dete rmining whether a tree has such a drawing; if such a drawing exists on e can be constructed in linear time in the real RAM model, The charact erization of Gabriel graphs settles several conjectures of Matula and Sokal [17].