Pancyclicity and NP-completeness in planar graphs (Q1962068): Difference between revisions

A graph is called {\(v\)-pancyclic} if it contains a cycle of length \(l\) containing a given vertex \(v\) for \(3\leq l\leq n\), and a graph \(G\) is called vertex pancyclic if \(G\) is \(v\)-pancyclic for all \(v\). The authors show that it is NP-complete to determine whether a 3-connected cubic planar graph is \(v\)-pancyclic for given vertex \(v\), it is NP-complete to determine whether a 3-connected cubic planar graph is pancyclic, and it is NP-complete to determine whether a 3-connected planar graph is vertex pancyclic. They also show that every maximal outplanar graph is vertex pancyclic.