output-sensitive algorithm for the edge-width of an embedded graph
Let G be an unweighted graph of complexity n cellularly embedded in a surface (orientable or not) of genus g . We describe improved algorithms to compute (the length of) a shortest non-contractible and a shortest non-separating cycle of G . 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 ) time, where k is the length of the cycle.
edge-width embedded graph surface face-width computational topology topological graph theory