English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Let G be a graph embedded on a surface of genus g with b boundary cycles. Wedescribe algorithms to compute multiple types of non-trivial cycles in G, usingdifferent techniques depending on whether or not G is an undirected graph. If Gis undirected, then we give an algorithm to compute a shortest non-separatingcycle in 2^O(g) n log log n time. Similar algorithms are given to compute ashortest non-contractible or non-null-homologous cycle in 2^O(g+b) n log log ntime. Our algorithms for undirected G combine an algorithm of Kutz with knowntechniques for efficiently enumerating homotopy classes of curves that may beshortest non-trivial cycles.  Our main technical contributions in this work arise from assuming G is adirected graph with possibly asymmetric edge weights. For this case, we give analgorithm to compute a shortest non-contractible cycle in G in O((g^3 + g b)nlog n) time. In order to achieve this time bound, we use a restriction of theinfinite cyclic cover that may be useful in other contexts. We also describe analgorithm to compute a shortest non-null-homologous cycle in G in O((g^2 + gb)n log n) time, extending a known algorithm of Erickson to compute a shortestnon-separating cycle. In both the undirected and directed cases, our algorithmsimprove the best time bounds known for many values of g and b.

Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs