EMBEDDING INTO THE RECTILINEAR GRID

Authors
BANDELT HJ CHEPOI V
Citation
Hj. Bandelt et V. Chepoi, EMBEDDING INTO THE RECTILINEAR GRID, Networks, 32(2), 1998, pp. 127-132
Citations number
11
Categorie Soggetti
Computer Science Hardware & Architecture","Computer Science Hardware & Architecture
Journal title
Networks → ACNP
ISSN journal
00283045
Volume
32
Issue
2
Year of publication
1998
Pages
127 - 132
Database
ISI
SICI code
0028-3045(1998)32:2<127:EITRG>2.0.ZU;2-B
Abstract
We show that the embedding of metric spaces into the I-1-grid Z(2) can be characterized in essentially the same fashion as in the case of th e I-1-plane R-2. In particular, a metric space can be embedded into Z( 2) iff every subspace with at most 6 points is embeddable. Moreover, i f such an embedding exists, it can be constructed in polynomial time ( for finite spaces). (C) 1998 John Wiley & Sons, Inc.