Polynomial time algorithms on circular‐arc overlap graphs
Toshinobu Kashiwabara, Sumio Masuda, Kazuo Nakajima, Toshio Fujisawa · Networks · 1991
Abstract Let S be a family of arcs on a circle. A graph G = (V,E) is called a circular‐arc overlap graph for S if (i) there is a one‐to‐one correspondence between V and S and (ii) two vertices in V are adjacent if and only if the corresponding arcs in S intersect but neither one of them contains the other. In this article, we present two polynomial time algorithms on circular‐arc overlap graphs. Given a circular‐arc overlap graph in the form of a family of n arcs, the first algorithm obtains a maximum independent set in O(n2) time and the second one finds a maximum clique in O(n5) time.