A crosslink is a double link established between the two entries of an edge in an adjacency list representation of a graph. Crosslinks play important roles in several parallel algorithms as they provide constant time access between the two entries of an edge; the existence of crosslinks is usually assumed. We consider the problem of establishing crosslinks in a crosslink-less adjacency list for graphs that belong to a class of graphs called the linearly contractible graphs, and show that cross-links can be established optimally in O(log n log*n) time using a CREW PRAM and optimally in O(log n) time using a CRCW PRAM for such graphs.

We present optimal parallel algorithms to find maximal matchings in two classes of sparse graphs, namely, graphs with bou.nded degree and those which, for some p, are forbidden to have the clique Kp as a minor. This latter class is quite large; for example, planar graphs satisfy this condition, as do graphs with any fixed bound on their genus. Our algorithms use O(log n) time on a CRCW PRAM for both classes of graphs. On an EREW PRAM, our algorithms use O(log n) time for graphs with bounded degree and O(log n log* n) time for graphs with forbidden Kp-minors.