English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Succinct Representations of Separable Graphs

Blelloch, G. E., & Farzan, A. (2010). Succinct Representations of Separable Graphs. In A. Amir, & L. Parida (Eds.), Combinatorial Pattern Matching (pp. 138-150). Berlin: Springer. doi:10.1007/978-3-642-13509-5_13.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-16F5-4 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-28AD-5
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Blelloch, Guy E.1, Author
Farzan, Arash2, Author           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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).

Details

show
hide
Language(s): eng - English
 Dates: 20102010
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 536766
DOI: 10.1007/978-3-642-13509-5_13
URI: http://dx.doi.org/10.1007/978-3-642-13509-5_13
Other: Local-ID: C1256428004B93B8-D6865F434DFCB112C1257816000198FF-Farzan2010a
 Degree: -

Event

show
hide
Title: 21st Annual Symposium on Combinatorial Pattern Matching
Place of Event: New York, NY
Start-/End Date: 2010-01-12 - 2011-01-12

Legal Case

show

Project information

show

Source 1

show
hide
Title: Combinatorial Pattern Matching
  Abbreviation : CPM 2010
  Subtitle : 21st Annual Symposium, CPM 2010
Source Genre: Proceedings
 Creator(s):
Amir, Amihood1, Editor
Parida, Laxmi1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 138 - 150 Identifier: ISBN: 978-3-642-13508-8

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 6129 Sequence Number: - Start / End Page: - Identifier: -