（B） ラベル配置アルゴリズムの設計
平面上に点，曲線，多角形などのオブジェクトが配置されているときに，それらの名前や属性などを示す文字列を適切な位置に
表示していくものとします．このとき，それらの文字列をラベルと呼び，ラベルの表示位置を求める問題をラベル配置問題と呼んで
います．本研究室では，この問題について，
（B-1） 地図中への地名などの配置
（B-2） グラフ描画中への頂点名などの配置
という2種類の応用を考え，それぞれについてアルゴリズムの開発を行っています．
（B-1） 地図中への地名などの配置
近年電子地図が広く利用されていますが，ラベルが表示領域の外周で切断されていたり，利用者にとって不要な情報が多すぎる，
あるいは，必要な情報が欠けているということがしばしばあります．そこで，利用者の要求に応じた適切な地図表示を実現するための
技術の一つとして，地図ラベルの自動配置アルゴリズムについて研究しています．
ラベルは，他のラベルや点，指定した障害物（表示領域の外周など）と重ならないように配置します．特定の種類の点のラベルを
強調して表示することも可能です．下図に，アルゴリズムの実行例を示します．このアルゴリズムは，Wagnerらによって開発された
アルゴリズムに改良を行ったもので，平面上の点のみをラベル付けの対象としています．すべての点にラベル付けすることが難しい
場合には，できるだけ多くの点にラベル付けすることを試みています．
地図ラベル配置アルゴリズムの実行例
本研究室では，このアルゴリズムの拡張を行い，以下の機能をもったアルゴリズムの開発を行っています．
・ 各点の重要度が指定されているとき，重要度の総和が大きくなるようにラベルを配置
・ 引き出し線を用いたラベル配置
・ ラベルの縦書き表示や，長いラベルを2行に折り返して表示
・ 線情報（鉄道，道路などに対応）へのラベル配置
・ 指定された割合以上の点のラベルを配置できる範囲で，文字のサイズをできるだけ大きくして表示
［発表論文］
・ “地点の優先度を考慮した地図ラベル配置アルゴリズム” 電子情報通信学会論文誌(A), vol. J88-A, pp. 677-681 (2005).
・ “引出し線を用いたラベル配置,” 電子情報通信学会論文誌(A), vol. J89-A, pp. 268-275 (2006).
・ “一般化したラベルサイズ最大化問題に対するアルゴリズム,” 電子情報通信学会論文誌(A), vol. J91-A, pp. 1223-1228 (2008).
・ “ラベル配置可能領域とルール処理を用いたラベル配置アルゴリズム,” 電子情報通信学会論文誌(A), vol.J92-A, pp.699-704 (2009).
など
（B-2） グラフ描画中への頂点名などの配置
グラフ描画に対し，頂点及び辺のラベルを配置するアルゴリズムを開発しています．下図はラベル配置の簡単な
例です．ここでは，各ラベルを長方形で表しています．
グラフ描画へのラベル配置の例
ラベル配置の対象が頂点だけであったとしても，接続している辺や周辺の頂点・辺が障害物となるため，ラベル表示位置を
決める際には様々な工夫をしています．また，最初からラベルのサイズのことを考慮に入れて，ラベル付きグラフの描画を
求めるアルゴリズムも設計しています．
［発表論文］
・ “グラフ描画における辺のラベルの配置法,” 電子情報通信学会論文誌(A), vol. J85-A, pp. 306-314 (2002).
・ “辺がラベルをもつ無向グラフの描画法,” 電子情報通信学会論文誌(A), vol. J86-A, pp. 848-859 (2003).
・ “Placement of vertex labels in a graph drawing,” IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, vol. J87-A, pp. 2774-2779 (2004).
・ “グラフ描画へのラベル配置アルゴリズムの実験的評価,” 電子情報通信学会論文誌(A), vol. J88-A, pp. 671-676 (2005).
・ “An algorithm for drawing a graph with vertex labels,” Proc. 7th Japan-Korea Workshop on Algorithms and Computation, Sendai, Japan, pp. 267-275 (2003).
・ “全頂点のラベルを配置したグラフ描画を求めるアルゴリズム,” 電子情報通信学会論文誌(A), vol. J95-A (2012), 掲載予定.
など