Premium
Embedding into the rectilinear grid
Author(s) -
Bandelt HansJürgen,
Chepoi Victor
Publication year - 1998
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199809)32:2<127::aid-net5>3.0.co;2-d
Subject(s) - embedding , subspace topology , metric space , grid , metric (unit) , mathematics , plane (geometry) , space (punctuation) , computer science , discrete mathematics , combinatorics , topology (electrical circuits) , theoretical computer science , artificial intelligence , geometry , mathematical analysis , engineering , operations management , operating system
We show that the embedding of metric spaces into the l 1 ‐grid ℤ 2 can be characterized in essentially the same fashion as in the case of the l 1 ‐plane ℝ 2 . In particular, a metric space can be embedded into ℤ 2 iff every subspace with at most 6 points is embeddable. Moreover, if such an embedding exists, it can be constructed in polynomial time (for finite spaces). © 1998 John Wiley & Sons, Inc. Networks 32: 127–132, 1998