Characterizing non-edges with a single interval of attainable Euclidean lengths in 3 dimensions.
We settle a decade-old conjecture and completely characterize graphs G and their non-edges f such that across all 3-dimensional Euclidean realizations of a given G-linkage, f attains lengths in a single interval. More precisely, given any assignment of (Euclidean) edge-lengths for G, f attains a single interval of length values across all 3-dimensional point configurations for which the pairwise distances agree with the given edge lengths. Although related to the minor-closed class of so-called 3-flattenable graphs, this class is not minor closed, has no obvious well quasi-ordering, and there are infinitely many minimal graphs-nonedge pairs - w.r.t. edge contractions - in the complement class. Our characterization overcomes these obstacles, is based on the 2 forbidden minors of the class of 3-flattenable graphs, and
contributes to the theory of Cayley configurations used for analyzing distance-constrained configuration spaces in a range of application domains. Based on this result, generalizations to higher dimensions and efficient algorithmic characterizations will be discussed.
(This is Joint work with William Sims.)