Finding Shortest Non-Separating and Non-Contractible Cycles for Topologically Embedded Graphs |
| |
Authors: | Sergio Cabello Bojan Mohar |
| |
Institution: | (1) Department of Mathematics, Institute for Mathematics, Physics and Mechanics, University of Ljubljana, 1000, Ljubljana, Slovenia;(2) Department of Mathematics, Faculty of Mathematics and Physics, University of Ljubljana, 1000, Ljubljana, Slovenia |
| |
Abstract: | We present an algorithm for finding shortest surface non-separating cycles in graphs embedded on surfaces in
time, where V is the number of vertices in the graph and g is the genus of the surface. If
, this represents an improvement over previous results by Thomassen, and Erickson and Har-Peled. We also give algorithms to
find a shortest non-contractible cycle in
time, which improves previous results for fixed genus. This result can be applied for computing the face-width and the non-separating
face-width of embedded graphs. Using similar ideas we provide the first near-linear running time algorithm for computing the
face-width of a graph embedded on the projective plane, and an algorithm to find the face-width of embedded toroidal graphs
in
time. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|