A Square Time Algorithm for Cyclic Edge Connectivity of Planar Graphs

Dingjun Lou1
1 Department of Computer Science Sun Yatsen University Guangzhou 510275 People’s Republic of China

Abstract

In this paper, we introduce an \(O(n^2)\) time algorithm to determine the cyclic edge connectivity of a planar graph, where \(n\) is the order of the planar graph. This is the first correct square time algorithm for cyclic edge connectivity of planar graphs.