Finding Cycles with Topological Properties in Embedded Graphs
Sergio Cabello, Éric Colin de Verdière, Francis Lazarus · SIAM Journal on Discrete Mathematics · 2011
Let G be a graph cellularly embedded on a surface $\mathcal{S}$. We consider the problem of determining whether G contains a cycle (i.e., a closed walk without repeated vertices) of a certain topological type in $\mathcal{S}$. We show that the problem can be answered in linear time when the topological type is one of the following: contractible, noncontractible, or nonseparating. In each case, we obtain the same time complexity if we require the cycle to contain a given vertex. On the other hand, we prove that the problem is NP-complete when considering separating or splitting cycles. We also show that deciding the existence of a separating or a splitting cycle of length at most k is fixed-parameter tractable with respect to k plus the genus of the surface.