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.

BibTeX

@InProceedings{RelaxedGabriel_CCCG2009,
  AUTHOR        = {Prosenjit Bose and Jean Cardinal and S{\'e}bastien Collette
                   and Erik D. Demaine and Bel{\'e}n Palop and Perouz Taslakian
                   and Norbert Zeh},
  TITLE         = {Relaxed {Gabriel} Graphs},
  BOOKTITLE     = {Proceedings of the 21st Canadian Conference on
                   Computational Geometry (CCCG 2009)},
  bookurl       = {http://www.cs.ubc.ca/conferences/CCCG09/},
  ADDRESS       = {Vancouver, British Columbia, Canada},
  MONTH         = {August 17--19},
  YEAR          = 2009,
  PAGES         = {169--172},

  length        = {4 pages},
  unrefereed    = 1,
  dblp          = {https://dblp.org/rec/conf/cccg/BoseCCDPTZ09},
  ee            = {http://cccg.ca/proceedings/2009/cccg09_44.pdf},
}

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]