Algorithms for the edge-width of an embedded graph

作者：Cabello Sergio^*; de Verdiere Eric Colin; Lazarus Francis

来源：Computational Geometry-Theory and Applications, 2012, 45(5-6): 215-224.

DOI：10.1016/j.comgeo.2011.12.002

• Topological graph theory
• Computational topology
• Edge-width
• Face-width
• Embedded graph

Let G be an unweighted graph of complexity n embedded in a surface of genus g, orientable or not. We describe improved algorithms to compute a shortest non-contractible and a shortest non-separating cycle in G. %26lt;br%26gt;If k is an integer, we can compute such a non-trivial cycle with length at most k in O(gnk) time, or correctly report that no such cycle exists. In particular, on a fixed surface, we can test in linear time whether the edge-width or face-width of a graph is bounded from above by a constant. This also implies an output-sensitive algorithm to compute a shortest non-trivial cycle that runs in O(gnk(0)) time, where k(0) is the length of the cycle. %26lt;br%26gt;We also give an approximation algorithm for the shortest non-trivial cycle. If a parameter 0 %26lt; epsilon %26lt; 1 is given, we compute in O(gn/epsilon) time a non-trivial cycle whose length is at most 1 + epsilon times the length of the shortest non-trivial cycle.

• 出版日期2012-7