Nonseparating cycles in planar and Eulerian graphs

Attila Bernáth, Marcin Kamiński


A cycle $C \subseteq E$ in a graph $G=(V,E)$ is nonseparating if $G - C$ is connected (note that we only delete the edges of the cycle). We study the algorithmic problem of deciding whether a graph contains a nonseparating cycle. This problem was shown to be NP-complete in [Bernáth and Király, 2011]. We prove a lemma about this problem in planar graphs and we show that it is NP-complete in Eulerian graphs. The former problem was an open problem raised in [Bernáth and Király, 2011]; the latter is a natural question in the context of greedy improvements of feasible solutions to the graphic TSP Problem.

Previous version can be found here.

Bibtex entry:

AUTHOR = {Bern{\'a}th, Attila and Kamiński, Marcin},
TITLE = {Nonseparating cycles in planar and Eulerian graphs},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2014},
NUMBER = {TR-2014-05}

Last modification: 13.3.2018. Please email your comments to Tamás Király!