Optimal graph orientation with storage applications
O. Aichholzer, F. Aurenhammer, and G. Rote
We show that the edges of a graph with maximum edge density
can always be
oriented such that each vertex has in-degree at most
. 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-
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.