Finding short cycles in embedded graph in polynomial time

Abstract

Let 1 be the set of fundamental cycles of breadth-first-search trees in a graph G, and let 2 be the set of the sums of two cycles in 1. Then we show the following: (1) contains a shortest Π-twosided cycle in a Π-embedded graph G. This implies the existence of a polynomially bounded algorithm to find a shortest Π-twosided cycle in an embedded graph and thus solves an open problem of Mohar and Thomassen [Graphs on Surfaces, 2001, p. 112]. (2)  contains all the possible shortest even cycles in a graph G. Therefore, there are at most polynomially many shortest even cycles in any graph. (3) Let 0 be the set of all the shortest cycles of a graph G. Then is a subset of  . Furthermore, many types of shortest cycles are contained in . Infinitely many examples show that there are exponentially many shortest odd cycles, shortest Π-onesided cycles and shortest Π-twosided cycles in some (embedded) graphs.

Key words： Π-twosided cycle; breadth-first-search tree; embedded graph