It is well known that every maximal planar graph with at least 4 vertices is 3-connected. But for maximal 1-planar graphs we cannot ensure the high connectivity. (See is-there-any-maximal-1-planar-or-2-planar-graph-that-is-not-3-connected?)
A $1$-planar graph is a graph that can be drawn such that every edge has at most one crossing. A graph together with a 1-planar drawing is called 1-plane. A graph is maximal 1-plane if we cannot add any edge from the complement so that the resulting graph is 1-plane and simple.
We call the crossing-free edges red edges, and call the edges that are crossed blue edges. The red graph $G_R$ of $G$ is the subgraph induced by the red edges.
The following literature proves that any maximal 1-plane graph is 2-connected. (In fact, the authors prove a stronger result: A subgraph formed by all non-crossing edges is spanning and $2$-connected. But from the proof, the authors prove that maximal 1-plane graphs are $2$-connected first, and then prove the stronger result.)
- Eades, P., Hong, S., Kato, N., Liotta, G., Schweitzer, P., Suzuki, Y.: A linear time algorithmfor testing maximal 1-planarity of graphs with a rotation system. Theoret. Comput. Sci. 513, 65–76 (2013) doi.org/10.1016
I'm confused by the part that deals with proving that a maxmal 1-plane graph is 2-connected (see the proof for details in Theorem 3).
Theorem 3. In a maximal 1-planar embedding $ξ(G)$ of a graph $G$ with at least $3$ vertices, the red graph $G_R$ is biconnected and spans all vertices.
(a). Prove that $G_R$ spans all vertices.
(b). The confusing proof part. To prove biconnectivity, we first show that $G$ is biconnected. Lemma 1 implies that each face has two real vertices. By Lemma 2, if two real vertices are adjacent to the same virtual vertex in $G_P$ then there are two vertex-disjoint paths between the two real vertices. Thus to show biconnectivity of $G$, it suffices to show the following: If $v_1$, $v_2$ and $v_3$ are real vertices that, ignoring virtual vertices, appear consecutively in this order on a face of the planarization $G_P$ of $G$, then there is a path from $v_1$ to $v_3$ that avoids $v_2$. This is clear, since $v_1$ and $v_3$ are incident with the same face, and therefore are adjacent since $G$ is maximal.
(c). $G_R$ is 2-connected.
We know that a graph is $2$-connected if and only if there are at least $2$ vertex-disjoint paths between every pair of vertices.
In the above proof I feel that the author has adopted the idea. But I do not see that the two vertices considered by the author are arbitrary. Note that in the proof the two vertices chosen lie in a face in the 1-planar embedding $ξ(G)$. That is to say, why the authors say:
Thus to show biconnectivity of $G$, it suffices to show the following: If $v_1$, $v_2$ and $v_3$ are real vertices that, ignoring virtual vertices, appear consecutively in this order on a face of the planarization $G_P$ of $G$, then there is a path from $v_1$ to $v_3$ that avoids $v_2$.
Why are two vertices that do not lie in the same face (may contains crossing point) not considered?
PS:
As shown in the figure, the authors consider two vertices that lie in the same face. Indeed, there are two vertex-disjoint paths between two vertices in the case ($v_1$ and $v_2$; $v_1$ and $v_3$).
Lemma 1. Let ξ(G) be a 1-planar embedding of a 1-planar graph $G$ on at least $2$ vertices, and $G_P$ be the planarization of $G$. Each face $f$ of $G_P$ has at least two real vertices.
Lemma 2. Let $G$ be a maximal 1-plane graph. If $v_1$ and $v_2$ are consecutive neighbors of a virtual vertex $w$ in the planarization $G_P$ of $G$, then there are two internally vertex-disjoint red paths (that is, paths consisting of red edges) from $v_1$ to $v_2$.
