On computing the vertex connectivity of 1-plane graphs

A graph is called 1-plane if it has an embedding in the plane where each edge is crossed at most once by another edge. A crossing of a 1-plane graph is called an × -crossing if the endpoints of the crossing pair of edges induce a matching. In this paper, we show how to compute the vertex connectivity of a 1-plane graph G without × -crossings in linear time. To do so, we show that for any two vertices u, v in a minimum separating set S , the distance between u and v in an auxiliary graph Λ( G ) (obtained by planarizing G and then inserting into each face a new vertex adjacent to all vertices of the face) is small. It hence suﬃces to search for a minimum separating set in various subgraphs Λ i of Λ( G ) with small diameter. Since Λ( G ) is planar, the subgraphs Λ i have small treewidth. Each minimum separating set S then gives rise to a partition of Λ i into three vertex sets with special properties; such a partition can be found via Courcelle’s theorem in linear time.