Homology, Homotopy and Applications

Volume 14 (2012)

Number 1

Computing braid groups of graphs with applications to robot motion planning

Pages: 159 – 180

DOI: https://dx.doi.org/10.4310/HHA.2012.v14.n1.a8


Vitaliy Kurlin (Department of Mathematical Sciences, Durham University, Durham, United Kingdom)


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.


graph, braid group, configuration space, fundamental group, homotopy type, deformation retraction, collision free motion, planning algorithm, complexity, robotics

2010 Mathematics Subject Classification

05C25, 20F36, 57M05

Published 13 July 2012