An optimal algorithm for finding maximum induced bipartite subgraphs of circular-arc graphs
Si-Qing Zheng · 2003
Given an intersection model S, which is a family of n arcs around a circle, of a circular-arc graph G, this algorithm requires O(n logn) time and O(n) space, if the endpoints of arcs are not sorted, and O(n) time is sufficient, if the endpoints of arcs are sorted.>