On the homotopy test on surfaces

Details On the homotopy test on surfaces On the homotopy test on surfaces

2011-10-20

arxiv.org/abs/1110.4573v2

Computer Science

Computational Geometry

33 pages, 11 figures

Scientific paper

Let G be a graph cellularly embedded in a surface S. Given two closed walks c and d in G, we take advantage of the RAM model to describe linear time algorithms to decide if c and d are homotopic in S, either freely or with fixed basepoint. We restrict S to be orientable for the free homotopy test, but allow non-orientable surfaces when the basepoint is fixed. After O(|G|) time preprocessing independent of c and d, our algorithms answer the homotopy test in O(|c|+|d|) time, where |G|, |c| and |d| are the respective numbers of edges of G, c and d. As a byproduct we obtain linear time algorithms for the word problem and the conjugacy problem in surface groups. We present a geometric approach based on previous works by Colin de Verdi\`ere and Erickson.

Affiliated with

Also associated with

No associations

Rating

On the homotopy test on surfaces does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the homotopy test on surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the homotopy test on surfaces will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-552267