Improved bounds on the oriented diameter of planar triangulations

Xiaonan Liu

arXiv:2608.19089v1 Primary: math.CO

Abstract

The oriented diameter of a connected bridgeless graph $G$, denoted by $\overrightarrow{\operatorname{diam}}(G)$, is the minimum diameter among all strong orientations of $G$. We study the oriented diameter of planar triangulations, and show that $\overrightarrow{\operatorname{diam}}(G)\leq \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{\operatorname{diam}}(G)\leq \frac{n+17}{3}$.

Disclosure

“t every n-vertex 5-connected planar triangulation −−−→ G has diam(G) ≤ 10 31 n + O(1). Acknowledgments The author is grateful to Xingxing Yu and Zhiyu Wang for helpful discussions on this prob- lem. The author used ChatGPT (OpenAI) in developing the face-coloring argument leading to Theorem 1.2 and language polishing. 15”
PDF page 15

Classification: Proof ideas or individual proof-step assistance
Multiplier: 8
Verified: 2026-08-22T18:19:55.981643Z

Structural counts

Pages 16 pdf

Theorems 4 source

Lemmas 2 source

Propositions 0 source

Corollaries 0 source

Definitions 0 source

Displayed equations 40 source

Bibliography entries 17 source

Appendix pages 0 estimated

Count notes

Source counts use the expanded primary TeX file main.tex.
Appendix pages include the first PDF page with an explicit Appendix heading through the final page.