Output-sensitive algorithm for the edge-width of an embedded graph
Sergio Cabello, Éric Colin de Verdière, Francis Lazarus · 2010
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.