Linear-time algorithms for problems on planar graphs with fixed disk dimension

Faisal N. Abu-Khzam, and Michael A. Langston
Information Processing Letters
Volume 101, Issue 1, 16 January 2007, Pages 36-40
http://dx.doi.org/10.1016/j.ipl.2006.08.006

ACiD2005論文のジャーナル版．
Fellows and Langston (1988) の不思議な論文で提案された「平面的グラフのdisk dimension」という概念について，disk dimensionが有界な平面的グラフに対するアルゴリズムを提案している．
平面的グラフGのdisk dimensionとは，Gが平面上のk個の開円板の補集合上に埋め込むことができ，さらにその埋め込みにおいて全ての頂点がk個の円板のいずれかの境界上に置かれるようにできる，という性質を持つ最小のkのことである．
まず，disk dimensionがkの平面的グラフが与えられたとき，そこから高々2k-2個の頂点を取り除くことでグラフを外平面的にできることが示されている．
これはアルゴリズムを与えることで証明されていて，そのアルゴリズムの計算量はO(3^k n)である (nは頂点数) ．
これを前処理として用いることで，外平面的グラフに対して易しい問題を解くアルゴリズムも提案されている．