L_ 1-embeddability of rectilinear polygons with holes

DOI10.1007/BF01222679MaRDI QIDQ1919299zbMATH OpenOpenAlexFDO

Authors Victor Chepoi, Vitalii Patlatîi, Chiril Prisăcaru

Publication date 13 April 1997

Published in Journal of Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01222679

zbMATH Keywords

metric spacerectilinear polyhedron

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Metric spaces, metrizability (54E35)

Review text

A plane polygon is rectilinear iff all its edges are axis-parallel. The authors endow a rectilinear polyhedron with the intrinsic metric and prove that the resulting metric space embeds in an \(L_1\) space.

Recommendations

• Embedding into the rectilinear grid
• Embedding into the rectilinear plane in optimal \(O(n^{2})\) time
• Embedding metric spaces in the rectilinear plane: a six-point criterion

Cites work

• \(\ell_ 1\)-rigid graphs
• Distance-preserving subgraphs of hypercubes
• Espaces Métriques Plongeables Dans Un Hypercube: Aspects Combinatoires
• scientific article; zbMATH DE number 439012 (Why is no real title available?)
• scientific article; zbMATH DE number 512480 (Why is no real title available?)
• Rectilinear shortest paths in the presence of rectangular barriers
• The cut cone,L1 embeddability, complexity, and multicommodity flows

Cited in

(2)

• scientific article; zbMATH DE number 1488854 (Why is no real title available?)
• None of the coronoid systems can be isometrically embedded into a hypercube

This page was built for publication: \(L_ 1\)-embeddability of rectilinear polygons with holes

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