On the oriented diameter of near planar triangulations

A directed graph $D=(V(D),A(D))$ is a graph with a vertex set $V(D)$ and an edge set $A(D)$ consisting of ordered pairs of vertices, called arcs or directed edges. We use $uv$ to denote the arc $(u,v)$, i.e., the arc oriented from $u$ to $v$. Given an undirected graph $G=(V(G),E(G))$, an orientation of $G$ is a directed graph such that each edge in $E(G)$ is assigned an direction. Given a (directed) graph $D$ and two vertices $u,v\in V(D)$, the distance from $u$ to $v$ in $D$, denoted by $d_{D}(u,v)$, is the number of edges of a shortest (directed) path from $u$ to $v$ in $D$. We often ignore the subscript if there is no ambiguity on the underlying graph. Given a (directed) graph $D$, the diameter of $D$ is defined to be $\text{diam}(D)=\max\{d_{D}(u,v):u,v\in V(D)\}$.

Given an undirected graph $G$ and $v\in V(G)$, let $N_{G}(v)$ denote the neighborhood of $v$ in $G$, and let $N_{G}[v]:=N_{G}(v)\cup\{v\}$. An edge $e\in E(G)$ is called a bridge if $G-e$ is disconnected. A graph is called bridgeless if contains no bridge.

A directed graph $D$ is called strongly connected if for any two vertices $u,v\in V(D)$, there exists a directed path from $u$ to $v$. Robbins [27], showed in 1939 that every bridgeless graph has a strongly connected orientation. The oriented diameter of a graph $G$, denoted by $\overrightarrow{\text{diam}}(G)$, is defined as

$$\overrightarrow{\text{diam}}(G)=\min\{\text{diam}(D):\textrm{$D$ is a strongly connected orientation of $G$}\}.$$

An orientation $D$ of $G$ is called optimal if $\overrightarrow{\text{diam}}(G)=\text{diam}(D)$. Note that $\overrightarrow{\text{diam}}(G)\geq\text{diam}(G)$.

Chvátal and Thomassen [5], showed in 1978 that determining the oriented diameter of a given graph is NP-complete. In the same paper, Chvátal and Thomassen showed that every bridgeless graph $G$ with diameter $d$ satisfies $\overrightarrow{\text{diam}}(G)\leq 2d^{2}+2d$, and there exist bridgeless graphs of diameter $d$ for which every strong orientation has diameter of at least $\frac{1}{2}d^{2}+d$. The upper bound was recently improved by Babu, Benson, Rajendraprasad and Vaka [1] to $1.373d^{2}+6.971d-1$.

The paper by Chvátal and Thomassen [5] has led to further investigations of such bounds on the oriented diameter with respect to other graph parameters, including the diameter [12, 16, 20], the radius [4], the domination number [11, 21], the maximum degree [9], the minimum degree [2, 8, 28], the number of edges of the graph [7], and other graph classes [3, 13, 14, 15, 16, 17, 19, 22, 23, 24, 26, 29, 30]. See the survey by Koh and Tay [18] for more information on some of these results.

In this paper, we study the oriented diameter of planar graphs, in particular near triangulations. A near triangulation is a plane graph such that every face except possibly the outer face is bounded by a triangle. An outerplanar graph is a planar graph such that every vertex lies on the boundary of the outer face. Let $K_{4}^{-}$ denote the graph obtained from $K_{4}$ by deleting an arbitrary edge. Let $W_{5}$ be the wheel graph on six vertices obtained by connecting every vertex of a $C_{5}$ to a new vertex. Let $G_{6}^{1},G_{6}^{2},G_{6}^{3},G_{8}^{1}$ be the graphs in Figure 1. In [30], Wang, Chen, Dankelmann, Guo, Surmacs and Volkmann showed the following theorem on the oriented diameter of (edge-)maximal outerplanar graphs.

Recently, Mondal, Parthiban and Rajasingh [25] studied the oriented diameter of planar triangulations, which are the maximal planar graphs. They showed the following theorem.

They [25] asked whether the upper bound could be improved. In this paper, we determine a tight upper bound (except for seven small exceptions) on the oriented diameter of a $2$-connected near triangulation.

Note that both maximal outerplanar graphs and planar triangulations are $2$-connected near triangulations. Therefore, Theorem 1.3 extends Theorem 1.1 and improves the upper bound in Theorem 1.2. Moreover, by Theorem 1.1, there exist $n$-vertex maximal outerplanar graphs (which are near triangulations) that have oriented diameter $\lceil n/2\rceil$ for every integer $n$ with $n\geq 5$. Hence the upper bound in Theorem 1.3 is tight.

Organization and terminology. In Section 2, we show some lemmas about the structure of near triangulations with certain outer cycle. In Section 3, we give a proof of Theorem 1.3. For convenience, for the rest of the paper, we assume that a near triangulation is $2$-connected, i.e., its outer face is bounded by a cycle. We conclude this section with some terminology and notation. For any positive integer $k$, let $[k]:=\{1,2,\ldots,k\}$. Let $G$ be a plane graph. The outer walk of $G$ consists of vertices and edges of $G$ incident with the outer face of $G$. If the outer walk is a cycle in $G$, we call it outer cycle instead. For a cycle $C$ in $G$, we use $\overline{C}$ to denote the subgraph of $G$ consisting of all vertices and edges of $G$ contained in the closed disc in the plane bounded by $C$. The interior of $C$ is then defined as the subgraph $\overline{C}-C$. For any distinct vertices $u,v\in V(C)$, we use $uCv$ to denote the subpath of $C$ from $u$ to $v$ in clockwise order.

The following lemma is clear, we state it below without proof.

In [30], Wang et.al. applied induction on the number of vertices to show Theorem 1.1 and they observed three structures that help reduce a maximal outerplanar graph to a graph with fewer vertices. Observe that those structures can also help reduce a near triangulation. Note that every degree-$2$ vertex $v$ in a near triangulation is contained in its outer cycle $C$ and $N(v)\subseteq V(C)$.

The next lemma follows from Theorem 1.1.

We also show the following lemma, which describes some structural properties of certain near triangulations.

We will show Theorem 1.3 by induction on the number of vertices in $G$. Theorem 1.3 for near triangulations on $n\leq 8$ vertices are confirmed by computer searches¹¹1See the code in https://github.com/wzy3210/Oriented_diameter.. So we assume that $n\geq 9$. Let $G_{0}$ be an $n$-vertex near triangulation with $n\geq 9$. Note that $G$ is not one of the graphs in $\{K_{4}^{-},K_{4},W_{5},G_{6}^{1},G_{6}^{2},G_{6}^{3},G_{8}^{1}\}$. Let $C_{0}$ be the outer cycle of $G_{0}$. We remove an edge $e=uw\in E(C_{0})$ from $C_{0}$ if there exists a vertex $v\in V(G_{0})\backslash V(C_{0})$ such that $v,u,w$ form a facial triangle. Note that $G_{0}-e$ is an $n$-vertex $2$-connected near triangulation with the outer cycle $(C_{0}-e)\cup uvw$. We perform the same process on $G-e$ and repeat this process until we get an $n$-vertex $2$-connected near triangulation $G$ with outer cycle $C$ such that there is no vertex $v$ in $V(G)\backslash V(C)$ that forms a facial triangle with some $e\in E(C)$. By Lemma 2.1, $\overrightarrow{\text{diam}}(G_{0})\leq\overrightarrow{\text{diam}}(G)$ since $G$ is a spanning subgraph of $G_{0}$. Hence it suffices to show that $\overrightarrow{\text{diam}}(G)\leq\left\lceil\frac{n}{2}\right\rceil$.

Suppose $V(G)\backslash V(C)=\emptyset$. Then $G$ is a maximal outerplanar graph on at least $9$ vertices, and we have $\overrightarrow{\text{diam}}(G)\leq\left\lceil\frac{n}{2}\right\rceil$ by Theorem 1.1. Hence we may assume that $V(G)\backslash V(C)\neq\emptyset$. Let $A$ be the set of vertices of degree two in $G$ (which all lie on $C$). It follows from Lemma 2.7 that $|A|\geq 3$. If $|A|\geq 4$, by Lemmas 2.3, we apply induction on $G-A^{\prime}$, where $A^{\prime}\subseteq A$ and $|A^{\prime}|=4$. Note that $G-A^{\prime}$ is a smaller near triangulation on at least $5$ vertices such that $G-A^{\prime}$ is not outerplanar and hence $\overrightarrow{\text{diam}}(G)\leq\overrightarrow{\text{diam}}(G-A^{\prime})+2\leq\left\lceil\frac{n}{2}\right\rceil$ unless $G-A^{\prime}\in\{W_{5},G_{6}^{3}\}$. If $G-A^{\prime}\in\{W_{5},G_{6}^{3}\}$, we know that $n=10$ and the outer cycle of $G-A^{\prime}$ has length five. Since $|A^{\prime}|=4$, there exist two degree-$2$ vertices $u,v$ in $G$ such that $N(u)\cap N(v)\neq\emptyset$. Let $H=G-\{u,v\}$. Then it follows from Lemma 2.2 that $\overrightarrow{\text{diam}}(G)\leq\max\{\overrightarrow{\text{diam}}(H)+1,4\}$. Since $H=G-\{u,v\}$ is a near triangulation on $8$ vertices and $H$ is not outerplanar, $\overrightarrow{\text{diam}}(H)\leq\left\lceil\frac{8}{2}\right\rceil=4$. Therefore, $\overrightarrow{\text{diam}}(G)\leq 5$.

Now we assume that $|A|=3$. Let $S=\{v\in V(C):\text{ $v$ has a neighbor in $V(G)\backslash V(C)$}\}$. By Lemma 2.7, $|S|=3$ and $G[S]$ is a triangle such that all vertices in $V(G)\backslash V(C)$ are contained in the interior of $G[S]$. Let $T=G[S]=u_{1}u_{2}u_{3}u_{1}$ such that $u_{1},u_{2},u_{3}$ appear on $C$ in clockwise order. Note that $\overline{T}$ is a planar triangulation on at least $4$ vertices. For convenience, let $u_{4}=u_{1}$. Let $C_{i}:=u_{i}Cu_{i+1}u_{i}$ for each $i\in[3]$. We know that $O_{i}:=\overline{C_{i}}$ is a maximal outerplanar graph with $|V(O_{i})|\geq 3$. Since $G$ has exactly three degree-$2$ vertices, there is exactly one degree-$2$ vertex, say $v_{i}$, in $V(u_{i}Cu_{i+1})$ for every $i\in[3]$. Hence $A=\{v_{1},v_{2},v_{3}\}$.

Case 1: Suppose there are at least two $O_{i}$ with $|V(O_{i})|=3$. Without loss of generality, we may assume $|V(O_{1})|=|V(O_{2})|=3$. Then $v_{1}$ and $v_{2}$ have a common neighbor $u_{2}$. Let $H=G-\{v_{1},v_{2}\}$. Note that $H$ is a near triangulation on $n-2$ vertices (with $n-2\geq 7$) and $H$ is not outerplanar. This implies that $H$ is not one of the exception graphs, and hence, $\overrightarrow{\text{diam}}(H)\leq\left\lceil\frac{n-2}{2}\right\rceil$ by induction. It follows from Lemma 2.2 that $\overrightarrow{\text{diam}}(G)\leq\max\{\overrightarrow{\text{diam}}(H)+1,4\}\leq\left\lceil\frac{n}{2}\right\rceil$.

Case 2: Suppose there is exactly one $O_{i}$ with $|V(O_{i})|=3$ and we may assume that $|V(O_{3})|=3$, i.e., $O_{3}=v_{3}u_{1}u_{3}v_{3}$. Let $n_{i}:=|V(O_{i})|$ for each $i\in[2]$ and let $n_{T}:=|V(\overline{T})|$. Then $n_{i}\geq 4$ for $i\in[2]$ and $n_{T}\geq 4$. Since $n_{1}+n_{2}+n_{T}=n+3$, we have $n_{i}\leq n-5$ for $i\in[2]$ and $n_{T}\leq n-5$. First we orient the edges in $\overline{T}$. If $\overline{T}=K_{4}$, Lemma 2.6 implies there exists an orientation $D_{T}$ of $\overline{T}$ such that $\text{diam}(D_{T})=3=\frac{n_{T}}{2}+1$ and $\max\{d_{D_{T}}(u_{2},w),d_{D_{T}}(w,u_{2})\}\leq 2=\frac{n_{T}}{2}$. If $\overline{T}\neq K_{4}$, we apply induction to $\overline{T}$ and get an optimal orientation $D_{T}$ such that $\text{diam}(D_{T})\leq\left\lceil\frac{n_{T}}{2}\right\rceil$. Therefore, we give an orientation $D_{T}$ of $\overline{T}$ such that $\text{diam}(D_{T})\leq\frac{n_{T}}{2}+1$ and $\max\{d_{D_{T}}(u_{2},w),d_{D_{T}}(w,u_{2})\}\leq\left\lceil\frac{n_{T}}{2}\right\rceil$. Next we orient the two edges incident with $v_{3}$ by making $O_{3}$ a directed triangle. Now we orient the edges in $O_{i}-u_{i}u_{i+1}$ for $i\in[2]$. Since $O_{i}$ is maximal outerplanar, $O_{i}$ has an orientation $D_{i}$ such that $\text{diam}(D_{i})\leq\frac{n_{i}}{2}+1$ and $\max\{d_{D_{i}}(u_{2},w),d_{D_{i}}(w,u_{2})\}\leq\left\lceil\frac{n_{i}}{2}\right\rceil$ by Lemma 2.5. Observe that $\overline{T}$ and $O_{i}$ have exactly one common edge for each $i\in[2]$. We can combine $D_{i}$ with $D_{T}$ (possibly by reversing the orientation of $D_{i}$). Therefore we get an orientation $D$ of $G$.

We claim that $\text{diam}(D)\leq\left\lceil\frac{n}{2}\right\rceil$. Let $u,v$ be any two distinct vertices in $G$.

Suppose both $u$ and $v$ are in $V(O_{i})$ where $i\in[2]$. We know that $d_{D}(u,v)\leq d_{D_{i}}(u,v)\leq\frac{n_{i}}{2}+1\leq\frac{n-5}{2}+1\leq\left\lceil\frac{n}{2}\right\rceil$. Similarly, if $u,v\in V(\overline{T})$, then $d_{D}(u,v)\leq d_{D_{T}}(u,v)\leq\frac{n_{T}}{2}+1\leq\frac{n-5}{2}+1\leq\left\lceil\frac{n}{2}\right\rceil$. Now we assume that one of $u,v$ is in $V(O_{i})$ where $i\in[2]$, and one is in $V(\overline{T})$. Without loss of generality, let $u\in V(O_{i})$ and $v\in V(\overline{T})$. Then

	$\displaystyle d_{D}(u,v)$	$\displaystyle\leq d_{D}(u,u_{2})+d_{D}(u_{2},v)$
		$\displaystyle=d_{D_{i}}(u,u_{2})+d_{D_{T}}(u_{2},v)$
		$\displaystyle\leq\left\lceil\frac{n_{i}}{2}\right\rceil+\left\lceil\frac{n_{T}}{2}\right\rceil\leq\frac{n_{i}+n_{T}}{2}+1=\frac{n+3-n_{3-i}}{2}+1$
		$\displaystyle\leq\frac{n-1}{2}+1\leq\frac{n+1}{2}.$

This implies $d_{D}(u,v)\leq\left\lceil\frac{n}{2}\right\rceil$. Similarly we can show $d_{D}(v,u)\leq\left\lceil\frac{n}{2}\right\rceil$; moreover, similarly we can show $d_{D}(u,v)\leq\left\lceil\frac{n}{2}\right\rceil$ when one of $u,v$ is in $V(O_{i})$ and one is in $V(O_{3-i})$ for each $i\in[2]$. Now suppose $v_{3}\in\{u,v\}$ and we may assume $u=v_{3}$. If $v\in O_{3}$, then $d_{D}(u,v)\leq 2\leq\lceil\frac{n}{2}\rceil$. If $v\in V(O_{i})$ where $i\in[2]$, then

$$d_{D}(v_{3},v)\leq d_{D}(v_{3},u_{2i-1})+d_{D}(u_{2i-1},v)\leq 2+\frac{n_{i}}{2}+1=\frac{n_{i}}{2}+3\leq\frac{n-5}{2}+3=\frac{n+1}{2}.$$

Similarly, we can show that $d_{D}(v,v_{3})\leq\frac{n+1}{2}$ and that $\max\{d_{D}(v_{3},v),d_{D}(v,v_{3})\}\leq\frac{n+1}{2}$ if $v\in V(\overline{T})$. Hence for any $u,v\in V(G)$, $d_{D}(u,v)\leq\left\lceil\frac{n}{2}\right\rceil$, i.e., $\text{diam}(D)\leq\left\lceil\frac{n}{2}\right\rceil$. Therefore, $\overrightarrow{\text{diam}}(G)\leq\text{diam}(D)\leq\left\lceil\frac{n}{2}\right\rceil$.

Case 3: Suppose $|V(O_{i})|\geq 4$ for all $i\in[3]$. Then since $O_{i}$ is outerplanar and $v_{i}$ is the only degree-$2$ vertex in $O_{i}$, it follows that $v_{i}$ must have a neighbor $v_{i}^{\prime}$ in $O_{i}$ such that $d_{G}(v_{i}^{\prime})=3$ and $v_{i}^{\prime}\in V(O_{i})\backslash\{u_{i},u_{i+1}\}$. Let $H:=G-\{v_{1},v_{1}^{\prime},v_{2},v_{2}^{\prime},v_{3},v_{3}^{\prime}\}$. Note that $H$ is a near triangulation on $n-6$ vertices and $H$ is not outerplanar. If $H\notin\{K_{4},W_{5},G_{6}^{3}\}$, we apply induction to $H$ and then $\overrightarrow{\text{diam}}(H)\leq\left\lceil\frac{n-6}{2}\right\rceil$. Thus it follows from Lemma 2.4 that $\overrightarrow{\text{diam}}(G)\leq\overrightarrow{\text{diam}}(H)+3\leq\left\lceil\frac{n-6}{2}\right\rceil+3\leq\left\lceil\frac{n}{2}\right\rceil.$ Now we assume that $H\in\{K_{4},W_{5},G_{6}^{3}\}$. Observe that $H\neq W_{5}$ as $\overline{T}\subseteq H$. Since $H\in\{K_{4},G_{6}^{3}\}$, there exists a unique choice of the embedding of $\overline{T}$ in $H$. It follows that there are at least two $O_{i}$ such that $O_{i}=K_{4}^{-}$ and we may assume $O_{1},O_{3}$ are $K_{4}^{-}$. Let $H^{\prime}=G-\{v_{1},v_{1}^{\prime},v_{3},v_{3}^{\prime}\}$. Observe that $u_{1}\in V(O_{1})\cap V(O_{3})$ and $u_{1}$ is contained in the outer cycle of $H^{\prime}$, say $C^{\prime}$, and $d_{H^{\prime}}(u_{1})=3$ and $u_{1}$ has a neighbor in $V(H^{\prime})\setminus V(C^{\prime})$. Recall that $H\in\{K_{4},G_{6}^{3}\}$. If $H=K_{4}$, we know that $n=10$ and $H^{\prime}=G_{6}^{3}$. By Lemma 2.6, there exists an orientation $D^{\prime}$ of $H^{\prime}$ such that $\text{diam}(D^{\prime})=\overrightarrow{\text{diam}}(H^{\prime})=4=\frac{n}{2}-1$ and $\max\{d_{D}(u_{1},w),d_{D}(w,u_{1})\}\leq 3=\frac{n}{2}-2$ for all $w\in V(H^{\prime})$. If $H=G_{6}^{3}$, $n=12$ and $H^{\prime}$ is a near triangulation on $8$ vertices such that $H^{\prime}$ is not outerplanar. By induction, $\overrightarrow{\text{diam}}(H^{\prime})\leq 4=\frac{n}{2}-2$. Therefore, $H^{\prime}$ has an orientation $D^{\prime}$ such that $\text{diam}(D^{\prime})\leq\frac{n}{2}-1$ and $\max\{d_{D^{\prime}}(u_{1},w),d_{D^{\prime}}(w,u_{1})\}\leq\frac{n}{2}-2$. For $i=1,3$, $O_{i}=K_{4}^{-}$ and $O_{i}$ has an orientation $D_{i}$ such that $\text{diam}(D_{i})=3$ and by Lemma 2.5, $\max\{d_{D_{i}}(u_{1},w),d_{D_{i}}(w,u_{1})\}\leq 2$ for every $w\in V(O_{i})$. Combine $D_{1},D_{3},D^{\prime}$ and we get an orientation $D$ of $H$. It is not hard to check $\text{diam}(D)\leq\frac{n}{2}$. Therefore, $\overrightarrow{\text{diam}}(G)\leq\text{diam}(D)\leq\left\lceil\frac{n}{2}\right\rceil$. This completes the proof.