Back to Search Start Over

On the oriented diameter of near planar triangulations

Authors :
Ge, Yiwei
Liu, Xiaonan
Wang, Zhiyu
Publication Year :
2023

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.

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2312.03258
Document Type :
Working Paper