TY - GEN
T1 - Shortest non-trivial cycles in directed surface graphs
AU - Erickson, Jeff
PY - 2011
Y1 - 2011
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 -