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