Optimal graph orientation with storage applications

O. Aichholzer, F. Aurenhammer, and G. Rote

Abstract:

We show that the edges of a graph with maximum edge density $d$ can always be oriented such that each vertex has in-degree at most $d$. Hence, for arbitrary graphs, edges can always be assigned to incident vertices as uniformly as possible. For example, in-degree 3 is achieved for planar graphs. This immediately gives a space-optimal data structure that answers edge membership queries in a maximum edge density-$d$ graph in $O(\log d)$ time.

Reference: O. Aichholzer, F. Aurenhammer, and G. Rote. Optimal graph orientation with storage applications. SFB-Report F003-51, SFB 'Optimierung und Kontrolle', TU Graz, Austria, 1995.