Finding short cycles in embedded graph in polynomial time

DOI10.1007/S11464-010-0003-YMaRDI QIDQ977665zbMATH OpenOpenAlexFDO

Authors Han Ren, Ni Cao

Publication date 23 June 2010

Published in Frontiers of Mathematics in China (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0807.1620

zbMATH Keywords

\(\Pi\)-twosided cycleembedded graphbreadth-first-search tree

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Abstract: Let ${calC}_1$ be the set of fundamental cycles of breadth-first-search trees in a graph $G$ and ${calC}_2$ the set of the sums of two cycles in ${calC}_1$. Then we show that $$ contains a shortest $Pi$-twosided cycle in a $Pi$-embedded graph $G$;$(2)$ $calC$ contains all the possible shortest even cycles in a graph $G$;$(3)$ If a shortest cycle in a graph $G$ is an odd cycle, then $calC$ contains all the shortest odd cycles in $G$. This implies the existence of a polynomially bounded algorithm to find a shortest $Pi-$twosided cycle in an embedded graph and thus solves an open problem of B.Mohar and C.Thomassen[2,pp112]

Recommendations

• Finding shortest contractible and shortest separating cycles in embedded graphs
• Finding shortest contractible and shortest separating cycles in embedded graphs
• Ford-Fulkerson algorithm and short cycles in embedded graphs
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Shortest enclosing walks and cycles in embedded graphs
• Finding a shortest cycle in a subspace of the cycle space of a graph
• A polynomial-time approximation scheme for embedding hypergraph in a cycle
• Finding short cycles in planar graphs using separators
• Finding cycles with topological properties in embedded graphs
• Finding shortest non-separating and non-contractible cycles for topologically embedded graphs

Cites work

• Embeddings of graphs with no short noncontractible cycles
• Graph theory with applications
• Graphs on surfaces

Cited in

(8)

• Finding a shortest even hole in polynomial time
• Finding even cycles faster via capped k-walks
• Short cycle structures for graphs on surfaces and an open problem of Mohar and Thomassen
• Ford-Fulkerson algorithm and short cycles in embedded graphs
• Algorithms – ESA 2005
• A note on finding a shortest complete cycle in an undirected graph
• scientific article; zbMATH DE number 6027233 (Why is no real title available?)
• Finding a shortest cycle in a subspace of the cycle space of a graph

This page was built for publication: Finding short cycles in embedded graph in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q977665)