Fast Algorithm for Realizing Linkages of Planar Graphs

Meera Sitharam, University of Florida

Workshop on Progress and Open Problems in Rigidity Theory

Date and Time: Thursday, February 25, 2021 - 11:15am to 12:00pm

Abstract: Finding 2 dimensional realizations of linkages (graphs with edge lengths) is a problem with many applications, but difficult algorithmically for multiple reasons: there are exponentially many potential realizations, determining existence of a realization is NP^R-complete, and even finding good recursive decompositions of the graph - so-called optimal DR-plans - is NP-complete.

We show that for a large class of planar graphs (a) a realization "type" can be specified that isolates a realization and (b) an algorithm exists to find the realization, given the type, whose running time is polynomial in the size of the input graph and a natural measure of accuracy of realization.

The algorithm is based on two results of independent interest. (i) A combinatorial theorem that the graphs in the class can be recursively decomposed into nearly rigid graphs (i.e., they have so-called constant flex DR-plans) that additionally have a nice Cayley configuration space (technically the base space of a branched covering map of the variety of realizations), a concept related to the flattenability of graphs. (ii) A semi-numeric algorithm that performs a search of the Cayley configuration space restricted to regions specified by critical points, which are used to define the input realization type.