Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Does anybody know of any results on succinct data structures for triangulations that can be constructed efficiently, and preferably also updated efficiently?
Does anybody know of practical implementations of succinct data structures for triangulations?
Is there a good and up-to-date survey that discusses this topic?
Regarding practical implementations of Luca's representation, he says that:
Unfortunately, the amount of auxiliary bits needed by the encoding becomes asymptotically negligible only for very huge graphs, which makes succinct representations of mainly theoretical interest.
(Excerpt from "Explicit array-based compact data structures for triangulations", by Luca C. Aleardi and Olivier Devillers, INRIA Research Report 7736, 2011, URL: http://hal.inria.fr/hal-00678615).
You may also check Mebarki's thesis for practical results: http://tel.archives-ouvertes.fr/tel-00336178/.
Take a look at the theoretical work of Castelli et al. and also the latest papers of J. Barbay.
"Luca Castelli Aleardi, Olivier Devillers, Gilles Schaeffer: Succinct Representation of Triangulations with a Boundary. WADS 2005: 134-145"
"Luca Castelli Aleardi, Olivier Devillers, Gilles Schaeffer: Dynamic updates of succinct triangulations. CCCG 2005: 134-137"
"Jérémy Barbay, Luca Castelli Aleardi, Meng He, J. Ian Munro: Succinct Representation of Labeled Graphs. Algorithmica 62(1-2): 224-257 (2012)"
For the implementation side, i would check CGAL and its triangulation data structures.
