On a class of metrics related to graph layout problems

DOI10.1016/j.laa.2010.06.038zbMath1222.05036arXiv0709.0910OpenAlexW2005376048WikidataQ57702215 ScholiaQ57702215MaRDI QIDQ603106

Gerhard Reinelt, Adam N. Letchford, Dirk Oliver Theis, Hanna Seitz

Publication date: 5 November 2010

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

metric spacesconvex analysispolyhedral combinatoricsgraph layout problems

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)

Related Items

On the facial structure of symmetric and graphical traveling salesman polyhedra

Cites Work

• Unnamed Item
• Unnamed Item
• An improved approximation ratio for the minimum linear arrangement problem
• \(\ell ^2_2\) spreading metrics for vertex ordering problems
• A canonical decomposition theory for metrics on a finite set
• The hypermetric cone is polyhedral
• Generating lower bounds for the linear arrangement problem
• Fréchet embeddings of negative type metrics
• Remarks to Maurice Frechet's article ``Sur la definition axiomatique d'une classe d'espaces vectoriels distancies applicables vectoriellement sur l'espace de Hilbert
• Decorous Lower Bounds for Minimum Linear Arrangement
• Divide-and-conquer approximation algorithms via spreading metrics
• Improved lower bounds for embeddings into L₁
• New Approximation Techniques for Some Linear Ordering Problems
• On the cut polytope
• Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
• Euclidean distortion and the sparsest cut
• The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁
• Geometry of cuts and metrics