MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Blelloch, Guy E.
Farzan, Arash
dblp
dblp
Not MPG Author(s):
Blelloch, Guy E.
Editor(s):
Amir, Amihood
Parida, Laxmi
dblp
dblp
Not MPII Editor(s):
Amir, Amihood
Parida, Laxmi
BibTeX cite key*:
Farzan2010a
Title, Booktitle
Title*:
Succinct Representations of Separable Graphs
Booktitle*:
Combinatorial Pattern Matching : 21st Annual Symposium, CPM 2010
Event, URLs
Conference URL::
Downloading URL:
http://dx.doi.org/10.1007/978-3-642-13509-5_13
Event Address*:
New York, NY
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
12 January 2010
Event End Date:
12 January 2011
Publisher
Name*:
Springer
URL:
Address*:
Berlin
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
6129
Number:
Month:
Pages:
138-150
Year*:
2010
VG Wort Pages:
ISBN/ISSN:
978-3-642-13508-8
Sequence Number:
DOI:
10.1007/978-3-642-13509-5_13
Note, Abstract, ©
(LaTeX) Abstract:
We consider the problem of highly space-efficient representation of separable graphs while supporting queries in constant time in the RAM with logarithmic word size. In particular, we show constant-time support for adjacency, degree and neighborhood queries. For any monotone class of separable graphs, the storage requirement of the representation is optimal to within lower order terms. Separable graphs are those that admit a $O(n^c)$-separator theorem where $c < 1$. Many graphs that arise in practice are indeed separable. For instance, graphs with a bounded genus are separable. In particular, planar graphs (genus $0$) are separable and our scheme gives the first succinct representation of planar graphs with a storage requirement that matches the information-theory minimum to within lower order terms with constant time support for the queries. We, furthers, show that we can also modify the scheme to succinctly represent the combinatorial planar embedding of planar graphs (and hence encode planar maps).
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Farzan2010a,
AUTHOR = {Blelloch, Guy E. and Farzan, Arash},
EDITOR = {Amir, Amihood and Parida, Laxmi},
TITLE = {Succinct Representations of Separable Graphs},
BOOKTITLE = {Combinatorial Pattern Matching : 21st Annual Symposium, CPM 2010},
PUBLISHER = {Springer},
YEAR = {2010},
VOLUME = {6129},
PAGES = {138--150},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {New York, NY},
ISBN = {978-3-642-13508-8},
DOI = {10.1007/978-3-642-13509-5_13},
}


Entry last modified by Anja Becker, 01/18/2011
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
01/12/2011 01:17:27 AM
Revisions
2.
1.
0.

Editor(s)
Anja Becker
Anja Becker
Arash Farzan

Edit Dates
18.01.2011 14:12:07
13.01.2011 13:21:45
01/12/2011 01:17:27 AM