Computing braid groups of graphs with applications to robot motion planning (Q424856)

The author describes an algorithm producing presentations of graph braid groups (the fundamental groups of configuration spaces associated to graphs). The paper also suggests a motion planning algorithm for many particles (robots) moving along a graph avoiding collisions; the complexity of this algorithm is linear in the number of edges and is quadratic in the number of robots. The author also shows that the 2-point braid groups associated to \textit{light} planar graphs admit presentations where all relations are commutators. A graph \(G\) is said to be \textit{light} if any cycle \(C\) of \(G\) contains an open edge \(h\) such that any cycle of \(G-\bar h\) is disjoint from \(C\).