On Flattenability of Graphs

DOI10.1007/978-3-319-21362-0_9zbMATH Open1439.05166OpenAlexW1520555415MaRDI QIDQ3452282FDOQ3452282

Authors Meera Sitharam, Joel Willoughby

Publication date 11 November 2015

Published in Automated Deduction in Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.01489

zbMATH Keywords

\(d\)-dimensional rigidity matroid\(d\)-flattenability of graphs

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35) Graph representations (geometric and intersection representations, etc.) (05C62) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

Abstract: We consider a generalization of the concept of $d$-flattenability of graphs - introduced for the $l_2$ norm by Belk and Connelly - to general $l_p$ norms, with integer $P$, $1lep<infty$, though many of our results work for $l_{i}nfty$ as well. The following results are shown for graphs $G$, using notions of genericity, rigidity, and generic $d$-dimensional rigidity matroid introduced by Kitson for frameworks in general $l_p$ norms, as well as the cones of vectors of pairwise $l_p^p$ distances of a finite point configuration in $d$-dimensional, $l_p$ space: (i) $d$-flattenability of a graph $G$ is equivalent to the convexity of $d$-dimensional, inherent Cayley configurations spaces for $G$, a concept introduced by the first author; (ii) $d$-flattenability and convexity of Cayley configuration spaces over specified non-edges of a $d$-dimensional framework are not generic properties of frameworks (in arbitrary dimension); (iii) $d$-flattenability of $G$ is equivalent to all of $G$'s generic frameworks being $d$-flattenable; (iv) existence of one generic $d$-flattenable framework for $G$ is equivalent to the independence of the edges of $G$, a generic property of frameworks; (v) the rank of $G$ equals the dimension of the projection of the $d$-dimensional stratum of the $l_p^p$ distance cone. We give stronger results for specific norms for $d=2$: we show that (vi) 2-flattenable graphs for the $l_1$-norm (and $l_{i}nfty$-norm) are a larger class than 2-flattenable graphs for Euclidean $l_2$-norm case and finally (vii) prove further results towards characterizing 2-flattenability in the $l_1$-norm. A number of conjectures and open problems are posed.

Recommendations

• Regularity properties of Levi flat graphs
• scientific article; zbMATH DE number 1743966
• scientific article; zbMATH DE number 475620
• On almost-planar graphs
• Flip graphs of bounded-degree triangulations
• Connectivity of triangulation flip graphs in the plane
• On the plane-width of graphs
• scientific article; zbMATH DE number 1019602

Cites work

• scientific article; zbMATH DE number 501471 (Why is no real title available?)
• scientific article; zbMATH DE number 1984325 (Why is no real title available?)
• Characterizing graphs with convex and connected Cayley configuration spaces
• Coordinate shadows of semidefinite and Euclidean distance matrices
• Extensions of Lipschitz mappings into a Hilbert space
• Faces of the cone of Euclidean distance matrices: characterizations, structure and induced geometry
• Finite and infinitesimal rigidity with polyhedral norms
• Graph minors. XX: Wagner's conjecture
• Graph rigidity via Euclidean distance matrices
• Isometric embedding in \(\ell_ p\)-spaces
• Minimum dimension embedding of finite metric spaces
• ON THE CONJECTURE OF KEVIN WALKER
• On Khot’s unique games conjecture
• On bar frameworks, stress matrices and semidefinite programming
• On the impossibility of dimension reduction in l ₁
• Problems of distance geometry and convex properties of quadratic maps
• Realizability of graphs in three dimensions
• Remarks to Maurice Frechet's article ``Sur la definition axiomatique d'une classe d'espaces vectoriels distancies applicables vectoriellement sur l'espace de Hilbert
• Rounding Semidefinite Programming Hierarchies via Global Correlation
• Sum-of-squares proofs and the quest toward optimal algorithms
• Symmetry groups, semidefinite programs, and sums of squares
• The Rigidity of Graphs
• The cut cone,L1 embeddability, complexity, and multicommodity flows
• The topology of spaces of polygons

Cited in

(10)

• On flatness of the Coxeter graph \(E_ 8\)
• Infinitesimal Rigidity in Normed Planes
• Unavoidable minors for graphs with large \(\ell_p\)-dimension
• Infinitesimal rigidity and prestress stability for frameworks in normed spaces
• The rigidity of infinite graphs
• Symmetric isostatic frameworks with \(\ell^1\) or \(\ell^\infty\) distance constraints
• Levi-flat graphs with a noncompact boundary
• Homothetic packings of centrally symmetric convex bodies
• The excluded minors for isometric realizability in the plane
• Characterizing graphs with convex and connected Cayley configuration spaces

This page was built for publication: On Flattenability of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452282)