  In edge orientations, the goal is usually to orient (direct) the edges of an
undirected $n$-vertex graph $G$ such that all out-degrees are bounded. When the
graph $G$ is fully dynamic, i.e., admits edge insertions and deletions, we wish
to maintain such an orientation while keeping a tab on the update time. Low
out-degree orientations turned out to be a surprisingly useful tool, with
several algorithmic applications involving static or dynamic graphs.
  Brodal and Fagerberg (1999) initiated the study of the edge orientation
problem in terms of the graph's arboricity, which is very natural in this
context. They provided a solution with constant out-degree and \emph{amortized}
logarithmic update time for all graphs with constant arboricity, which include
all planar and excluded-minor graphs. However, it remained an open question
(first proposed by Brodal and Fagerberg, later by others) to obtain similar
bounds with worst-case update time.
  We resolve this 15 year old question in the affirmative, by providing a
simple algorithm with worst-case bounds that nearly match the previous
amortized bounds. Our algorithm is based on a new approach of a combinatorial
invariant, and achieves a logarithmic out-degree with logarithmic worst-case
update times. This result has applications in various dynamic graph problems
such as maintaining a maximal matching, where we obtain $O(\log n)$ worst-case
update time compared to the $O(\frac{\log n}{\log\log n})$ amortized update
time of Neiman and Solomon (2013).

Data Structures and Algorithms