Embedding into the rectilinear grid

Journal Article


We show that the embedding of metric spaces into the l1‐grid ℤ2 can be characterized in essentially the same fashion as in the case of the l1‐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

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.