Finding short cycles in embedded graph in polynomial time

Abstract

Let [graphic not available: see fulltext] be the set of fundamental cycles of breadth-first-search trees in a graph G, and let [graphic not available: see fulltext] be the set of the sums of two cycles in [graphic not available: see fulltext]. Then we show the following: (1) [graphic not available: see fulltext] 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) [graphic not available: see fulltext] 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 [graphic not available: see fulltext] be the set of all the shortest cycles of a graph G. Then [graphic not available: see fulltext] is a subset of [graphic not available: see fulltext]. Furthermore, many types of shortest cycles are contained in [graphic not available: see fulltext]. Infinitely many examples show that there are exponentially many shortest odd cycles, shortest Π-onesided cycles and shortest Π-twosided cycles in some (embedded) graphs.

Keywords

Π-twosided cycle / breadth-first-search tree / embedded graph

References

[1] Bondy J. A., Murty U. S. R. Graph Theory with Applications, 1978, London: Macmillan.

[2] Mohar B., Thomassen C. Graphs on Surfaces, 2001, Baltimore and London: The Johns Hopkins University Press.

[3] Thomassen C. Embeddings of graphs with no short noncontractible cycles. J of Combin Theory, 1990, 48: 155-177.