An algorithm is designed to write down presentations of graph braid groups. Generators are represented in terms of actual motions of robots moving without collisions on a given connected graph. A key ingredient is a new motion planning algorithm whose complexity is linear in the number of edges and is quadratic in the number of robots. The computing algorithm implies that 2-point braid groups of all light planar graphs have presentations where all relators are commutators.
Homology, Homotopy and Applications, Vol. 14 (2012), No. 1, pp.159-180.
Available as: dvi dvi.gz tar (dvi+eps) ps ps.gz pdf