MPI-I-94-148

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.