2009/08/07 by Vitaliy Kurlin, V. Kurlin, Kurlin, V. · 1 citation
Computer Science · Mathematics · #20F36 #57M05 #Advanced Graph Theory Research #Algebraic Topology (math.AT) #Computational Geometry and Mesh Generation #FOS: Mathematics #Geometric Topology (math.GT) #Topological and Geometric Data Analysis #math.AT #math.GT #msc:20F36 #msc:57M05
paper · pdf · doi:10.48550/arxiv.0908.1067
16 pages, 10 figures
arxiv created 2009/08/07 · openalex publication_date 2009/08/07 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We design an algorithm writing down presentations of graph braid groups. Generators are represented in terms of actual motions of robots moving without collisions on a given graph. A key ingredient is a new motion planning algorithm whose complexity is linear in the number of edges and 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.