The asymptotic maximum oriented diameter of graphs

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)\le 2d^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 \frac{1}{2}{d}^2+7d$ for every integer $d\ge 1$. This matches the leading coefficient of their lower bound and establishes $f(d)=\frac{1}{2}{d}^2+O(d)$, determining the optimal quadratic coefficient. Our proof gives a polynomial-time algorithm that constructs a strong orientation satisfying the stated bound.