# Item

ITEM ACTIONSEXPORT

Released

Report

#### Efficient computation of compact representations of sparse graphs

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

MPI-I-94-148.pdf

(Any fulltext), 149KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Arikati, S. R., Maheshwari, A., & Zaroliagis, C.(1994). *Efficient
computation of compact representations of sparse graphs* (MPI-I-94-148). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B530-E

##### Abstract

Sparse graphs (e.g.~trees, planar graphs, relative neighborhood graphs)
are among the commonly used data-structures in computational geometry.
The problem of finding a compact representation for sparse
graphs such that vertex adjacency can be tested quickly is fundamental to
several geometric and graph algorithms.
We provide here simple and optimal algorithms for constructing
a compact representation of $O(n)$ size for an $n$-vertex sparse
graph such that the adjacency can be
tested in $O(1)$ time. Our sequential algorithm
runs in $O(n)$ time, while the parallel one runs in $O(\log n)$ time using
$O(n/{\log n})$ CRCW PRAM processors. Previous results for this problem
are based on matroid partitioning and thus have a high complexity.