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?


2 Answers 2


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.