Computing braid groups of graphs with applications to robot motion planning
Vitaliy A. Kurlin · Homology Homotopy and Applications · 2012
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.