Farber's conjecture for planar graphs

2020/10/26 by Ben Knudsen, Knudsen, Ben
Computer Science · Mathematics · #Advanced Graph Theory Research #Digital Image Processing Techniques #Topological and Geometric Data Analysis #math.AT #math.GT

paper · pdf · doi:10.48550/arxiv.2010.13530

11 pages, 1 figure. Accepted for publication in Selecta Mathematica. May differ slightly from published from version

arxiv created 2021/08/02 · arxiv updated 2021/08/03

Abstract

We prove that the ordered configuration spaces of planar graphs have the highest possible topological complexity generically, as predicted by a conjecture of Farber. Our argument establishes the same generic maximality for all higher topological complexities. We include some discussion of the non-planar case, demonstrating that the standard approach to the conjecture fails at a fundamental level.

Related

• Farber's conjecture and beyond
• The topological complexity of pure graph braid groups is stably maximal
• Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
• Topological complexity of configuration spaces of fully articulated graphs and banana graphs
• Efficient Generation of Different Topological Representations of Graphs\n Beyond-Planarity