On Flattenability of Graphs

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

Joel Willoughby, Meera Sitharam

Publication date: 11 November 2015

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

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.

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

Recommendations

• Regularity properties of Levi flat graphs
• scientific article; zbMATH DE number 1743966
• Counting plane graphs: flippability and its applications
• Counting plane graphs: flippability and its applications
• 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

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)

Cites Work

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

Cited In (10)

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

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)