Dynamic Edge Orientation via Random Walks: From Trees to Outerplanar Graphs and Beyond

Gabriel Marques Domingues, Minh Hang Nguyen, Shay Solomon

We study the \emph{fully dynamic edge orientation problem}, focusing on \emph{worst-case} time bounds. An undirected graph undergoes edge insertions and deletions, and the goal is…