Artículo de revista
Succinct Representation of Labeled Graphs
Date
2012-02Registration in:
ALGORITHMICA Volume: 62 Issue: 1-2 Pages: 224-257 Published: FEB 2012
0178-4617
DOI: 10.1007/s00453-010-9452-7
Author
Barbay, Jérémy
Castelli Aleardi, Luca
He, Meng
Munro, J. Ian
Institutions
Abstract
In many applications, the properties of an object being modeled are stored as labels on vertices or edges of a graph. In this paper, we consider succinct representation of labeled graphs. Our main results are the succinct representations of labeled and multi-labeled graphs (we consider planar triangulations, planar graphs and k-page graphs) to support various label queries efficiently. The additional space cost to store the labels is essentially the information-theoretic minimum. As far as we know, our representations are the first succinct representations of labeled graphs. We also have two preliminary results to achieve the main contribution. First, we design a succinct representation of unlabeled planar triangulations to support the rank/select of edges in ccw (counter clockwise) order in addition to the other operations supported in previous work. Second, we design a succinct representation for a k-page graph when k is large to support various navigational operations more efficiently. In particular, we can test the adjacency of two vertices in O(lg k) time, while previous work uses O(k) time.