Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Efficient computation of compact representations of sparse graphs

Arikati, Srinivasa R. and Maheshwari, Anil and Zaroliagis, Christos D.

MPI-I-94-148. September 1994, 10 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s): KBytes; 148 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Arikati, Srinivasa R. and Maheshwari, Anil and Zaroliagis, Christos D.},
  TITLE = {Efficient computation of compact representations of sparse graphs},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-94-148},
  MONTH = {September},
  YEAR = {1994},
  ISSN = {0946-011X},