Testing vertex connectivity of bowtie 1-plane graphs

Abstract

A separating set of a connected graph $G$ is a set of vertices $S$ such that $G-S$ is disconnected. $S$ is a minimum separating set of $G$ if there is no separating set of $G$ with fewer vertices than $S$. The size of a minimum separating set of $G$ is called the vertex connectivity of $G$. A separating set of $G$ that is a cycle is called a separating cycle of $G$.

Let $G$ be a planar graph with a given planar embedding. Let $\Lambda(G)$ be a supergraph of $G$ obtained by inserting a face vertex in each face of $G$ and connecting the face vertex to all vertices on the boundary of the face. It is well known that a set $S$ is a minimum separating set of a planar graph $G$ if and only if the vertices of $S$ can be connected together using face vertices to get a cycle $X$ of length $2|S|$ that is separating in $\Lambda(G)$.

We extend this correspondence between separating sets and separating cycles from planar graphs to the class of bowtie 1-plane graphs. These are graphs that are embedded on the plane such that each edge is crossed at most once by another edge, and the endpoints of each such crossing induce either $K_4$, $K_4 \setminus \{e\}$ or $C_4$. Using this result, we give an algorithm to compute the vertex connectivity of a bowtie 1-plane graph in linear time.