Embedding into the rectilinear grid
Hans-J�rgen Bandelt, Victor D. Chepoi · Networks · 1998
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