**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- graph in
time.