# Succinct Representations of Arbitrary Graphs

@inproceedings{Farzan2008SuccinctRO, title={Succinct Representations of Arbitrary Graphs}, author={Arash Farzan and J. Ian Munro}, booktitle={ESA}, year={2008} }

We consider the problem of encoding a graph with nvertices and medges compactly supporting adjacency, neighborhood and degree queries in constant time in the logn-bit word RAM model. The adjacency query asks whether there is an edge between two vertices, the neighborhood query reports the neighbors of a given vertex in constant time per neighbor, and the degree query reports the number of incident edges to a given vertex.
We study the problem in the context of succinctness, where the goal is… Expand

#### Figures and Topics from this paper

#### 39 Citations

Succinct encoding of arbitrary graphs

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2013

A lower bound is proved in the cell probe model indicating it is impossible to achieve the information-theory lower bound up to lower order terms unless the graph is either too sparse or too dense. Expand

Succinct Representations of Separable Graphs

- Mathematics, Computer Science
- CPM
- 2010

This 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. Expand

Compact Navigation and Distance Oracles for Graphs with Small Treewidth

- Mathematics, Computer Science
- Algorithmica
- 2012

Given an unlabeled, unweighted, and undirected graph with n vertices and small (but not necessarily constant) treewidth k, we consider the problem of preprocessing the graph to build space-efficient… Expand

Compact Navigation and Distance Oracles for Graphs with Small Treewidth

- Mathematics, Computer Science
- ICALP
- 2011

Given an unlabeled, unweighted, and undirected graph with n vertices and small (but not necessarily constant) treewidth k, we consider the problem of preprocessing the graph to build space-efficient… Expand

Succinct Posets

- Mathematics, Computer Science
- ESA
- 2012

A succinct data structure for representing a poset that, given two elements, can report whether one precedes the other in constant time is designed, equivalent to succinctly representing the transitive closure graph of the poset. Expand

Succinct Representation of Trees and Graphs

- Mathematics
- 2009

In this thesis, we study succinct representations of trees and graphs. A succinct representation of a combinatorial object is a space efficient representation that supports a reasonable set of… Expand

Succinct Representation of Labeled Graphs

- Computer Science, Mathematics
- Algorithmica
- 2010

This paper designs 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. Expand

On the Succinct Representation of Equivalence Classes

- Mathematics, Computer Science
- Algorithmica
- 2016

Given a partition of an n element set into equivalence classes, we study the problem of assigning unique labels to these elements in order to support the query that asks whether the elements… Expand

Cell probe lower bounds for succinct data structures

- Computer Science, Mathematics
- SODA
- 2009

A new technique is developed for proving lower bounds for succinct data structures, where the redundancy in the storage can be small compared to the information-theoretic minimum, and the first insight into such problems is provided. Expand

Succinct Representation of Labeled Graphs

- Mathematics, Computer Science
- ISAAC
- 2007

This paper designs 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. Expand

#### References

SHOWING 1-10 OF 19 REFERENCES

Implicit Representation of Graphs

- Mathematics, Computer Science
- SIAM J. Discret. Math.
- 1992

In this chapter, the structure of the graph is completely encoded, so that, given the labels of two vertices, one can test if they are adjacent in time linear in the size of the labels. Expand

Compact representations of separable graphs

- Mathematics, Computer Science
- SODA '03
- 2003

A data structure for representing n-vertex unlabeled graphs that satisfy an O(nc)-separator theorem, c < 1 is described, which generalizes previous results for graphs with constant genus, such as planar graphs. Expand

Efficient Minimal Perfect Hashing in Nearly Minimal Space

- Mathematics, Computer Science
- STACS
- 2001

A simple randomized scheme that uses n log e+log log u+o(n+loglog u) bits and has constant evaluation time and O(n + log log u) expected construction time is presented. Expand

Optimal succinct representations of planar maps

- Computer Science, Mathematics
- SCG '06
- 2006

This paper proposes in particular the first optimal representations for 3-connected planar graphs and triangulations, which are the most standard classes of graphs underlying meshes with spherical topology. Expand

Succinct representation of balanced parentheses, static trees and planar graphs

- Mathematics, Computer Science
- Proceedings 38th Annual Symposium on Foundations of Computer Science
- 1997

This work considers the implementation of abstract data types for the static objects: binary tree, rooted ordered tree and balanced parenthesis expression and applies the approach to produce succinct representation of planar graphs in which one can test adjacency in constant time. Expand

Succinct indexes for strings, binary relations and multi-labeled trees

- Mathematics, Computer Science
- SODA '07
- 2007

This paper defines and design succinct indexes for several abstract data types, namely strings, binary relations and multi-labeled trees, and designs a succinct encoding that represents a string of length n over an alphabet of size σ using bits to support access/rank/select operations. Expand

Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses

- Computer Science, Mathematics
- ICALP
- 1998

Three sets of coding schemes which all take linear time for encoding and decoding are presented which are significantly shorter than the previously known results in each case. Expand

On the Size of Succinct Indices

- Mathematics, Computer Science
- ESA
- 2007

This paper presents several solutions to partially overcome the space occupancy problem of a succinct data structure, introducing new techniques of independent interest that allow us to improve over previously known upper and lower bounds. Expand

Adaptive Searching in Succinctly Encoded Binary Relations and Tree-Structured Documents

- Computer Science
- CPM
- 2006

This work shows that a succinct representation of the binary relation permits much better results, while using space within a lower order term of the optimal, in queries on semi-structured documents such as XML documents or file-system indexes. Expand

Optimal Bounds for the Predecessor Problem and Related Problems

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 2002

The lower bounds are proved for a large class of problems, including both static and dynamic predecessor problems, in a much stronger communication game model, but they apply to the cell probe and RAM models. Expand