Improved bounds on the oriented diameter of planar triangulations

Abstract

The oriented diameter of a connected bridgeless graph $G$, denoted by $\overrightarrow{\mathrm{diam}}(G)$, is the minimum diameter among all strong orientations of $G$. We study the oriented diameter of planar triangulations, and show that $\overrightarrow{\mathrm{diam}}(G)\le \frac{2n+44}{5}$ for any $n$-vertex planar triangulation $G$. This improves the leading constant in the previous best general upper bound $\lceil \frac{n}{2}\rceil$, due to Ge, Liu, and Wang, from $1/2$ to $2/5$. We also prove that every $n$-vertex $4$-connected planar triangulation satisfies $\overrightarrow{\mathrm{diam}}(G)\le \frac{n+17}{3}$.