Hole and antihole detection in graphs
Stavros D. Nikolopoulos, Leonidas Palios · 2004
In this paper, we study the problems of detecting holes and antiholes in general undirected graphs and present algorithms for them, which, for a graph on n vertices and m edges, run in O(n + m²) time and require O(nm) space; we thus provide a solution to the open problem posed by Hayward, Spinrad, and Sritharan in [12] asking for an O(n^4)- time algorithm for finding holes in arbitrary graphs. The key element of the algorithms is a special type of depthfirst search traversal which proceeds along P4 s (i.e., chordless paths on four vertices) of the input graph. We also describe a different approach which allows us to detect antiholes in graphs that do not contain chordless cycles on 5 vertices in O(n + m²) time requiring O(n +m) space. Our algorithms are simple and can be easily used in practice. Additionally, we show how our detection algorithms can be augmented so that they return a hole or an antihole whenever such a structure is detected in the input graph; the augmentation takes O(n +m) time and space.