Speaker
Description
Karthik Murali and Therese Biedl
Abstract: 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 X-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 X-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 \Lambda(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 suffices to search for a minimum separating set in various subgraphs \Lambda_i of \Lambda(G) with small diameter. Since \Lambda(G) is planar, the subgraphs \Lambda_i have small treewidth. Each minimum separating set S then gives rise to a partition of \Lambda_i into three vertex sets with special properties; such a partition can be found via Courcelle's theorem in linear time.