Paper by Erik D. Demaine

Reference:

Prosenjit Bose, Jean Cardinal, Sébastien Collette, Erik D. Demaine, Belén Palop, Perouz Taslakian, and Norbert Zeh, “Relaxed Gabriel Graphs”, in Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG 2009), Vancouver, British Columbia, Canada, August 17–19, 2009, pages 169–172.

Abstract:

We study a new family of geometric graphs that interpolate between the Delaunay triangulation and the Gabriel graph. These graphs share many properties with β-skeletons for β ∈ [0, 1] (such as sublinear spanning ratio) with the added benefit of planarity (and consequently linear size and local routability).

Length:

The paper is 4 pages.

Availability:

The paper is available in PDF (186k).

See information on file formats.

[Google Scholar search]