Edge‐Length Preserving Embeddings of Graphs Between Normed Spaces
Open Access
- 18 April 2026
- journal article
- Published by Wiley in Journal of Graph Theory
- Vol. 112 (4) , 491-506
Abstract
The concept of graph embeddability, initially formalized by Belk and Connelly and later expanded by Sitharam and Willoughby, extends the question of embedding finite metric spaces into a given normed space. A finite simple graph is said to be ‐embeddable if any set of induced edge lengths from an embedding of into a normed space can also be realised by an embedding of into a normed space . This property, being minor‐closed, can be characterized by a finite list of forbidden minors. Following the establishment of fundamental results about ‐embeddability, we identify sufficient conditions under which it implies independence with respect to the associated rigidity matroids for and . We show that the spaces and serve as two natural extreme spaces of embeddability and discuss ‐embeddability for varying . We provide a complete characterization of ‐embeddable graphs for the specific case when is 2‐dimensional and is infinite‐dimensional.Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- Unavoidable Minors for Graphs with Large $\ell _p$-DimensionDiscrete & Computational Geometry, 2021
- Graph Theory2017
- On Flattenability of Graphs2015
- Finite and Infinitesimal Rigidity with Polyhedral NormsDiscrete & Computational Geometry, 2015
- Embeddability of Snowflaked Metrics with Applications to the Nonlinear Geometry of the Spaces L p and ℓ p for 0<p<∞The Journal of Geometric Analysis, 2013
- Realizability of Graphs in Three DimensionsDiscrete & Computational Geometry, 2007
- Realizability of GraphsDiscrete & Computational Geometry, 2007
- Graph Minors .XIII. The Disjoint Paths ProblemJournal of Combinatorial Theory, Series B, 1995
- Potentials and isometric embeddings inL 1Israel Journal of Mathematics, 1976
- Les dimensions d'un ensemble abstraitMathematische Annalen, 1910