2 papers
cs.CG2022
On Computing Vertex Connectivity of 1-Plane Graphs
Therese Biedl, Karthik Murali
The vertex connectivity of a graph is the size of the smallest set of vertices such that is disconnected. For the class of planar graphs, the problem of ver…
math.CO2021
Computing the vertex connectivity of a locally maximal 1-plane graph in linear time
Therese Biedl, Karthik Murali
It is known that the vertex connectivity of a planar graph can be computed in linear time. We extend this result to the class of locally maximal 1-plane graphs: graphs that have an…