Report
Characterizing graph-nonedge pairs with single interval Cayley configuration spaces in 3-dimensions
| العنوان: | Characterizing graph-nonedge pairs with single interval Cayley configuration spaces in 3-dimensions |
|---|---|
| المؤلفون: | Sims, William, Sitharam, Meera |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Computational Geometry, Mathematics - Combinatorics |
| الوصف: | A linkage $(G,\ell)$ is a pair containing a finite simple undirected graph $G$ and a squared edge-length map $\ell$ that assigns squared Euclidean lengths to the edges of $G$. A $d$-realization of $(G,\ell)$ is an assignment of points in $\mathbb{R}^d$ to the vertices of $G$ for which pair-wise distances between points agree with $\ell$. For $d \leq 3$, we characterize pairs $(G,f)$, where $f$ is a nonedge of $G$, such that, for any squared edge-length map $\ell$, there is a single interval of attained distance values between the endpoints of $f$ over all $d$-realizations of $(G,\ell)$, answering a question posed in \cite{sitharam2010characterizing} a decade ago, which gave an equivalent characterization for $d\le 2$ that does not generalize to $d\ge 3$. Two notable byproducts of this characterization are a new tool for partial $3$-tree completion, a well-studied problem, and a deeper understanding of the realization space of partial $3$-tree linkages through the lens of Cayley realization spaces. Although related to the minor closed class of $3$-flattenable graphs, the class of pairs $(G,f)$ with the above property 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 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. Generalizations to higher dimensions and efficient algorithmic characterizations are conjectured. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2409.14227 |
| رقم الانضمام: | edsarx.2409.14227 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |