首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 $O(g^{3/2}V^{3/2}\log V+g^{5/2}V^{1/2})$ time, where V is the number of vertices in the graph and g is the genus of the surface. If $g=o(V^{1/3})$ , 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 $O(g^{O(g)}V^{3/2})$ 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 $O(V^{5/4}\log V)$ time.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号