Boundary labeling: Models and efficient algorithms for rectangular maps

Michael A. Bekos, Michael Kaufmann, Antonios Symvonis and Alexander Wolff
Computational Geometry
Volume 36, Issue 3, April 2007, Pages 215-236
http://dx.doi.org/10.1016/j.comgeo.2006.05.003

Graph Drawing 2004の論文．地図のラベル付け問題に関するはなし．

地図の周りにある余白にラベルを置いて，ラベルに対応する位置とラベル自身は線 (引き出し線) で結ぶ．
このようにしてラベル付けを行なうことを考える．(医療分野でもよく出現する描き方である．)
地図自体が長方形の場合を議論していて，特に，引き出し線の種類や最適化する目的関数などによって問題のヴァリエーションが出てくる．
まず制約として，引き出し線同士が交わらないこと，ラベル同士が交わらないこと，ラベルは長方形に接していることが要求される．
引き出し線の種類として (1) 直線，(2) 1回曲がることのできる軸平行な折れ線，(2) 2回曲がることのできる軸平行な折れ線 のどれを許すかでヴァリエーションがある．
また，引き出し線がラベルの境界上の指定された点に接続されるヴァージョンと，ラベルの境界上のどの点に接続してもよいヴァージョンがある．
そして，目的関数として，引き出し線の長さの総和の最小化，と引き出し線の曲がり数最小化がある．
また，地図の周りのどの部分にラベルを置くことができるか，という選択にもヴァリエーションがある．

1つ1つ結果を述べていくのは大変なので，詳細は論文を参照．論文の最後に未解決問題がいろいろと挙げられていて，研究をしようと思う人にはとても参考になる．