The Excluded Minors for Isometric Realizability in the Plane

DOI10.1137/16M1064775zbMath1358.05076arXiv1511.08054MaRDI QIDQ2968517

Samuel Fiorini, Tony Huynh, Gwenaël Joret, Antonios Varvitsiotis

Publication date: 16 March 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

isometric embeddings; finite metric spaces; graph minors

Mathematics Subject Classification ID

05C10: Planar graphs; geometric and topological aspects of graph theory

05C83: Graph minors

05C12: Distance in graphs

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

\(k\)-apices of minor-closed graph classes. I: Bounding the obstructions, Unavoidable minors for graphs with large \(\ell_p\)-dimension, Infinitesimal rigidity and prestress stability for frameworks in normed spaces, Rigidity of symmetric frameworks in normed spaces, On strict brambles

Cites Work

• Unnamed Item
• Graph minors. XX: Wagner's conjecture
• Isometric embedding in \(\ell_ p\)-spaces
• Realizability of graphs
• Realizability of graphs in three dimensions
• Finite and infinitesimal rigidity with polyhedral norms
• Minimum dimension embedding of finite metric spaces
• On Lipschitz embedding of finite metric spaces in Hilbert space
• Matroids and multicommodity flows
• Problems of distance geometry and convex properties of quadratic maps
• Graph minors. XIII: The disjoint paths problem
• Characterizing graphs with convex and connected Cayley configuration spaces
• On Flattenability of Graphs
• Bipartite Coverings of Graphs
• Decomposition of Finite Graphs Into Forests
• Geometry of cuts and metrics