On the oriented diameter of near planar triangulations

Yiwei Ge, Xiaonan Liu, Zhiyu Wang

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…