An Efficient Algorithm for Cyclic Edge Connectivity of Planar Graphs

A cyclic edge cutset is an edge cutset whose deletion disconnects the graph such that two of the components contain a cycle respectively. The cyclic edge connectivity clambda(G) is the minimum cardinality of all the cyclic edge cutsets of G. There is no polynomial time algorithm to determine the cyclic edge connectivity of a graph. In this paper,we develop a polynomial time algorithm to determine the cyclic edge connectivity of a planar graph. The time complexity of the algorithm is bounded by O(|V|²).