Low-Dimensional Embedding with Extra Information

Mihai Badoiu, Erik D. Demaine, MohammadTaghi Hajiaghayi and Piotr Indyk
Discrete and Computational Geometry
Issue Volume 36, Number 4 / December, 2006
Pages 609-632
http://dx.doi.org/10.1007/s00454-006-1268-5

SoCG2004特集号から．
距離空間の埋め込みに関する論文．

グラフと各辺の間の距離が与えられたとき，その距離を保ったままユークリッド平面上にグラフを埋め込む問題を考える．
グラフが完全グラフのとき，加法的歪みを最小にする埋め込みを擬多項式時間で見つけるアルゴリズムを与えている．
また，距離だけではなくて，角度や点の組合せ的位置関係 (順序タイプ) などが指定された場合の問題も考えている (というか，そちらが主である)．