PLANAR ORIENTATIONS WITH LOW OUT-DEGREE AND COMPACTION OF ADJACENCY MATRICES

We consider the problem of orienting the edges of a planar graph in such a way that the out-degree of each vertex is minimized. If, for each vertex upsilon, the out-degree is at most d, then we say that such an orientation is d-bounded. We prove the following results: Each planar graph has a 5-bounded acyclic orientation, which can be constructed in linear time. Each planar graph has a 3-bounded orientation, which can be constructed in linear time. A 6-bounded acyclic orientation, and a 3-bounded orientation, of each planar graph can each be constructed in parallel time O(log n log* n) on an EREW PRAM, using O(n/log n log* n) processors. As an application of these results, we present a data structure such that each entry in the adjacency matrix of a planar graph can be looked up in constant time. The data structure uses linear storage, and can be constructed in linear time.