Detecting a Theta or a Prism
Maria Chudnovsky, Rohan Kapadia · SIAM Journal on Discrete Mathematics · 2008
A theta in a graph is an induced subgraph consisting of two nonadjacent vertices joined by three disjoint paths. A prism in a graph is an induced subgraph consisting of two disjoint triangles joined by three disjoint paths. This paper gives a polynomial-time algorithm to test whether a graph has an induced subgraph that is either a prism or a theta.