TY - GEN

T1 - Shortest non-trivial cycles in directed surface graphs

AU - Erickson, Jeff

PY - 2011/7/15

Y1 - 2011/7/15

N2 - Let G be a directed graph embedded on a surface of genus g. We describe an algorithm to compute the shortest nonseparating cycle in G in O(g2n log n) time, exactly matching the fastest algorithm known for undirected graphs. We also describe an algorithm to compute the shortest noncontractible cycle in G in gO(g)n log n time, matching the fastest algorithm for undirected graphs of constant genus.

AB - Let G be a directed graph embedded on a surface of genus g. We describe an algorithm to compute the shortest nonseparating cycle in G in O(g2n log n) time, exactly matching the fastest algorithm known for undirected graphs. We also describe an algorithm to compute the shortest noncontractible cycle in G in gO(g)n log n time, matching the fastest algorithm for undirected graphs of constant genus.

KW - Computational topology

KW - Topological graph theory

UR - http://www.scopus.com/inward/record.url?scp=79960157830&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79960157830&partnerID=8YFLogxK

U2 - 10.1145/1998196.1998231

DO - 10.1145/1998196.1998231

M3 - Conference contribution

AN - SCOPUS:79960157830

SN - 9781450306829

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 236

EP - 243

BT - Proceedings of the 27th Annual Symposium on Computational Geometry, SCG'11

T2 - 27th Annual ACM Symposium on Computational Geometry, SCG'11

Y2 - 13 June 2011 through 15 June 2011

ER -