An algorithm for finding a large independent set in planar graphs
Norishige Chiba, Takao Nishizeki, Nobuji Saito · Networks · 1983
Abstract A subset of the vertices of a graph is independent if no two vertices in the set are adjacent. M. O. Albertson proposed an algorithm for finding an independent set that contains more than two‐ninth of the vertices of a planar graph. Refining his algorithm, we give an O (n 2 ) algorithm for the same purpose.