On the oriented diameter of near planar triangulations

Abstract

In this paper, we show that the oriented diameter of any $n$-vertex $2$-connected near triangulation is at most $\lceil \frac{n}{2}\rceil$ (except for seven small exceptions), and the upper bound is tight. This extends a result of Wang et.al. on the oriented diameter of maximal outerplanar graphs, and improves an upper bound of $n/2+O(\sqrt{n})$ on the oriented diameter of planar triangulations by Mondal, Parthiban and Rajasingh.