Algorithms for finding an induced cycle in planar graphs (Q653839)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Algorithms for finding an induced cycle in planar graphs |
scientific article |
Statements
Algorithms for finding an induced cycle in planar graphs (English)
0 references
19 December 2011
0 references
The induced cycle problem consists of finding an induced cycle, i.e., a cycle without a chord, passing through \(k\) given vertices. This problem is NP-complete in a general graph. In the paper the authors restrict themselves to planar graphs. For them is is proved that if \(k\) is fixed then the time complexity is linear. On the other hand if \(k\) is not fixed but \(k=o\left(\frac{\log n}{\log\log n}\right)^{\frac 23}\), where \(n\) is the number of vertices, then the induced cycle problem can be solved in \(O\left(n^{2+\varepsilon}\right)\) time for any \(\varepsilon>0\).
0 references
algorithm
0 references
planar graph
0 references
induced cycle
0 references
hole
0 references