The asymptotic maximum oriented diameter of graphs

Source abstract

The oriented diameter of a connected bridgeless graph is the minimum diameter of a strong orientation. Let $f(d)$ be the maximum oriented diameter among all such graphs of diameter $d$. In 1978, Chvátal and Thomassen proved $f(d)\le2d^2+2d$ and constructed graphs showing that any quadratic upper bound on $f(d)$ must have leading coefficient at least $1/2$. We prove that $f(d)\le \tfrac12d^2+7d$ for every integer $d\ge1$. This matches the leading coefficient of their lower bound and establishes $f(d)=\tfrac12d^2+O(d)$, determining the optimal quadratic coefficient. Our proof gives a polynomial-time algorithm that constructs a strong orientation satisfying the stated bound.