B₀-VPG Representation of
AT-free Outerplanar Graphs

After recalling some standard graph theoretic terminology in Section 1.2 and a brief literature review in Section 1.3, we layout our proofs in three sections. Section 2 has the B₀-VPG drawing procedure for biconnected outerpaths. Section 3 contains the characterization of linear outerplanar graphs. In Section 4, we prove that all AT-free outerplanar graphs are linear thereby completing the proof of the titular result. We conclude with Section 5, where we describe some necessary conditions for the existence of a B₀-VPG representation. This may help in characterizing B₀-VPG outerplanar graphs.

The closed neighborhood $N[v]$ of a vertex $v$ in a graph $G$ is the set containing $v$ and and its neighbors in $G$. A set of three independent vertices is called an asteroidal triple (AT) when there exists a path among each pair of them containing no vertex from the closed neighborhood of the third vertex. An AT-free graph is a graph which does not have an AT.

A plane graph is an embedding of a planar graph in the plane with no crossing edges. Let $G$ be a plane graph. The dual of $G$ is a graph that has a vertex for each face of $G$ and an edge between two of its vertices when the corresponding faces of $G$ share an edge. The weak dual of $G$ is obtained from its dual by removing the vertex corresponding to the outer face. An edge of $G$ incident to the outer face of $G$ is called a boundary edge and its endpoints are called boundary neighbors of each other. The remaining edges of $G$ are called internal edges. A leaf face is a face with at most one internal edge. A planar graph is outerplanar if it has a plane embedding in which all the vertices are incident on the outer face. Outerplanar graphs will always be drawn in such a way that the outer face contains all the vertices, and the terminology of faces, duals, weak duals, boundary edges and internal edges will be used assuming such a plane drawing. Let $G$ be an outerplanar graph. The weak dual of $G$ is a forest [16] and we denote it by $\mathcal{T}_{G}$. Further, we call $\mathcal{T}_{G}$ a linear forest if each component in $\mathcal{T}_{G}$ is a path.

Let $G$ be a graph. A $k^{+}$-vertex in $G$ is a vertex having at least $k$ neighbors in $G$. A leaf edge is an edge having one endpoint of degree one. A subgraph $H$ of $G$ is spanning if $V(H)=V(G)$, and induced if $E(H)=\{xy~{}|~{}x,y\in V(H),~{}xy\in E(G)\}$. A graph induced by a subset $S$ of the vertices of $G$ is denoted by $G[S]$. A subset of vertices in a graph is called a separator if its removal increases the number of components of the graph. A vertex $x$ is a cutvertex if $\{x\}$ is a separator. A graph is k-connected if it does not have a separator of size smaller than $k$. A graph is said to be connected (resp. biconnected) if it is 1-connected (resp. 2-connected). A block of a graph is a maximal biconnected subgraph of the graph. A trivial block is a block containing at most two vertices.

A graph $G$ is H-free if $G$ does not contain an induced subgraph isomorphic to $H$. A graph $G$ is said to be H-minor-free if it does not contain a minor isomorphic to $H$. We use $C_{k}$ to denote the simple cycle on $k$ vertices. A cycle on $k$ vertices $x_{0},\ldots,x_{k-1}$ where each $x_{i}$ is adjacent to $x_{i+1}$ (addition is modulo $k$) can also be denoted as $x_{0},\ldots,x_{k-1},x_{0}$. A $C_{4}$ together with an additional vertex $v$ adjacent to all the vertices of $C_{4}$ is called a 4-wheel. A triangular prism is the complement of $C_{6}$. An interval graph is an intersection graph of a set of intervals on $\mathbb{R}$.

The class B_k-VPG was introduced by Asinowski et al. in 2012 [3]. Nevertheless, these graphs were previously studied in various forms. One of them is grid intersection graphs (GIG) which are equivalent to bipartite B₀-VPG graphs. The recognition problem for string graphs and hence VPG graphs is NP-complete [24, 28]. The recognition problem for B₀-VPG graphs is NP-complete [25]. B₀-VPG characterizations are known for block graphs [2], split graphs, chordal bull-free graphs, chordal claw-free graphs [18] and cocomparability graphs [27].

Segment intersection graphs are intersection graphs of line segments in the plane. Chalopin and Gonçalves in 2009 showed that every planar graph is a segment intersection graph [9], confirming a conjecture of Scheinerman from 1984 [29]. One way to refine the class of segment intersection graphs is to restrict the number of directions permitted for the segments. If the number of directions is limited to two, we rediscover B₀-VPG. k-DIR graphs are intersection graphs of line segments that can lie in at most $k$ directions in the plane. It is known that bipartite planar graphs are $2$-DIR [21, 13, 14] and triangle-free planar graphs are $3$-DIR [7]. West conjectured that any planar graph is $4$-DIR [30] which was recently refuted by Gonçalves in 2020 [19]. Before the celebrated result by Gonçalves et al. that planar graphs are B₁-VPG [20], we had a chronology of results on B_k-VPG representation of planar graphs. Since $2$-DIR graphs are equivalent to B₀-VPG, bipartite planar graphs B₀-VPG. In [3], Asinowski et al. showed that planar graphs are B₃-VPG and conjectured that it is tight. Disproving this conjecture, Chaplick and Ueckerdt proved that planar graphs have a B₂-VPG representation [11]. This adds to the appeal for characterizing B₀-VPG planar graphs.

Outerpaths have many geometric representations like balanced circle-contact representations [1], geometric simultaneous embeddings with a matching [6], and partial geometric simultaneous embeddings with another outerpath [15]. All these representations will extend to linear outerplanar graphs because of Theorem 7 and Remark 2. Babu et al. provides an algorithm to augment outerplanar graphs of pathwidth $p$ to biconnected outerplanar supergraphs of pathwidth $\mathcal{O}(p)$ [4]. Connectivity augmentation of outerplanar graphs using minimum number of additional edges is studied in [17, 23]. Barát et al. have characterized the graphs with pathwidth at most two [5] and our class is a strict subclass of that.

We first prove that if an outerplanar graph $G$ is linear, then $G$ is cut-safe, block-safe and $\mathcal{T}_{G}$ is a linear forest. Our strategy is to look at the edges of $G$ which are forced to be internal edges in any biconnected outerplanar supergraph of $G$ and then use the fact that the internal edges in a biconnected outerpath have a natural linear order. It is easy to see that every internal edge of $G$, at least one edge in each face of $G$ (unless $G$ itself is a cycle), and all but at most two edges incident to any vertex of $G$ will all be internal edges in any biconnected outerplanar supergraph of $G$. We can say a bit more about edges incident to a cutvertex in a nontrivial block (Lemma 9) using the simple observation below. The extension of this simple observation to biconnected outerpaths (Observation 10) is a key to rest of this section.

For any three subsets $X,Y,Z$ of the vertices of a graph, $X$ separates $Y$ and $Z$ if every path between $Y$ and $Z$ contains a vertex from $X$.

Now we prove the other direction of Theorem 7. Let $G$ be a cut-safe and block-safe outerplanar graph such that $\mathcal{T}_{G}$ is a linear forest. We will construct a biconnected outerpath $G^{\prime}$ which contains $G$ as a subgraph. A connector between two nonadjacent boundary vertices $u$ and $v$ of a plane graph $H$ is either an edge $uv$ or a two-length path $(u,w,v)$ such that $w\notin V(H)$ drawn through the outer face. Hence the resultant graph is planar. In the following construction, if every connector used is an edge (resp. two-length path), then $G$ is contained as a spanning (resp. induced) subgraph of $G^{\prime}$. The construction of $G^{\prime}$ is done in two phases. Each phase consists of repeated applications of a single action.

Let us call the resulting graph $G_{2}$. In Case (a), the weak dual $\mathcal{T}_{B^{\prime}}$ of $B^{\prime}$ is a path formed by extending $\mathcal{T}_{B}$ with a leaf edge corresponding to the dual of $a_{i}b_{i}$. The new terminal edge in ${{B^{\prime}}}$ is in the new leaf face and hence the two terminal edges of ${{B^{\prime}}}$ are antipodal. Every component incident to $B$ in $G$ (except $C$) is incident to ${{B^{\prime}}}$ in $G_{2}$. Each such component associated to a terminal edge of $B$ can be associated to the corresponding terminal edge of ${{B^{\prime}}}$. In Case (b), the structure of ${{B^{\prime}}}$ is simple since every internal edge of ${{B^{\prime}}}$ is incident to $v$. It is easily verified that $\mathcal{T}_{B^{\prime}}$ is a path and ${{B^{\prime}}}$ is safe with the given terminals. Next we argue that $G_{2}$ is cut-safe. In Case (a), the only change to $\mathcal{C}_{v}$ in $G_{2}$ is that $C$ and the component $C_{B}$ containing $B$ merges into a single component $C_{{B^{\prime}}}$. But if $C_{B}$ is small for $v$ in $G$, then $C_{{B^{\prime}}}$ remains small for $v$ in $G_{2}$ and hence $v$ remains safe in $G_{2}$. In Case (b), since ${{B^{\prime}}}\setminus v$ is a path, ${{B^{\prime}}}$ is a small component for $v$ and $v$ is safe in $G_{2}$. Let $u\neq v$ be a cutvertex in $G_{2}$ and let $C_{u}$ be a small component incident to $u$. Since $C$ is a maximal small component, $C_{u}$ does not contain $C$ and hence $C_{u}$ remains unaffected (and hence small) in $G_{2}$. So $u$ remains safe in $G_{2}$.

We perform Action 1 once for each maximal small component incident to a cutvertex in $G$ to obtain a graph $G_{3}$. Note that for each cutvertex $v$ in $G_{3}$, each small component in $\mathcal{C}_{v}$ is a block. Also, each component incident to a nontrivial block $B$ in $G_{3}$ is incident at the second vertex of a terminal edge of $B$. For each trivial block $B=uv$ which is not a pendant edge of $G_{3}$, assign $(u,v)$ to be the first and $(v,u)$ to be the second terminal edge of $B$. Associate every component incident to $B$ at $u$ (resp. $v$) with terminal edge $(v,u)$ (resp. $(u,v)$).

Let us call the resulting graph $G_{4}$. The weak dual $\mathcal{T}_{B}$ of $B$ is a path obtained by connecting two leaf vertices of $\mathcal{T}_{B_{0}}$ and $\mathcal{T}_{B_{1}}$ through the dual vertex corresponding to the new bounded face. The new terminal edges of $B$ are antipodal in $B$. Every cutvertex other than $v$ in $B_{i}$ ($i\in\{0,1\}$) is contained in the second terminal edge of $B_{i}$ which continues to be a terminal edge in $B$. If $C_{i}$ is small for an $i\in\{0,1\}$, then $B_{i}=C_{i}$ and the second terminal edge of $B_{i}$ has $v$ as its second vertex. If both $C_{0}$ and $C_{1}$ are big for $v$, since $v$ is safe in $G_{3}$, there are no other components in $\mathcal{C}_{v}$. Hence $v$ is no longer a cutvertex in $G_{4}$. Hence all the cutvertices of $B$ are contained in its terminal edges and $B$ is safe. Now we argue that $G_{4}$ is cut-safe. The difference from $\mathcal{C}_{v}$ in $G_{3}$ to $\mathcal{C}_{v}$ in $G_{4}$ is that $C_{0}$ and $C_{1}$ gets merged into a single component. If both $C_{0}$ and $C_{1}$ are small components, then one can easily check that the new component is $B$ itself and it is small for $v$. Hence the number of big components in $\mathcal{C}_{v}$ does not increase and hence $v$ remains safe in $G_{4}$ or ceases to be a cutvertex. Let $u\neq v$ be a cutvertex in $G_{4}$ and let $C_{u}$ be a small component incident to $u$. Since $C_{u}$ is a block, it does not contain the cutvertex $v$ and hence remains unaffected (and thus small) in $G_{4}$. So $u$ remains safe in $G_{4}$.

We repeat Action 2 as long as there is a cutvertex. Let $G^{\prime}$ denote the resulting biconnected graph. Since each action preserves cut-safety, block-safety and linearity of the weak dual, $G^{\prime}$ is a biconnected outerpath. This completes the proof of Theorem 7.

By Theorem 7, any linear outerplanar graph can be realized as an induced subgraph of a biconnected outerpath. This together with Theorem 3 gives the following corollary.