Planar orientations with low out-degree and compaction of adjacency matrices.
M. Chrobak and D. Eppstein.
Theor. Comp. Sci. 86 (2): 243–266, 1991,
doi:10.1016/0304-3975(91)90020-3.
Describes efficient sequential and parallel algorithms for orienting the edges of an undirected planar graph so that each vertex has few outgoing edges. From such an orientation one can test in constant time whether a given edge exists. One consequence is a parallel algorithm to list all subgraphs isomorphic to \(K_3\) or \(K_4\). More recently this paper has been cited for its applications to scheduling update operations in parallel finite element methods.