Graph Drawing 2日目

今日も報告を

Representation of Planar Hypergraphs by Contacts of Triangles

H. de Fraysseix, P.O. de Mendez, and P. Rosenstiehl

線形ハイパーグラフ (つまりどの2辺も同じ2頂点を含まないようなハイパーグラフ) を考える．
ハイパーグラフが平面的であるとは，その頂点-辺接続グラフが平面的であることを言う．
既存の結果として，任意の平面的グラフが平面上の三角形の接触グラフとして表現できることが示されていたが，この論文ではそれを拡張して，任意の平面的線形ハイパーグラフが平面上の三角形と直線分の接触グラフとして表現できることを示した．
この発表中で言及されて始めて知ったが，「任意の平面的グラフが直線分の交差グラフとして表現できる」という長年の未解決問題が最近肯定的に解決されたようだ．

The Complexity of Several Realizability Problems for Abstract Topological Graphs

J. Kyncl

僕好みの論文．

グラフG=(V,E)のトポロジカル描画とは，その各辺が曲線として描かれているものである
(その他細かい条件があるけれどもここでは省略)．
抽象トポロジカルグラフとはグラフG=(V,E)と辺の非順序対の集合Rの対(G,R)である．
抽象トポロジカルグラフ(G,R)が実現可能であるとは，Gのトポロジカル描画で，その描画において交差する辺の対の集合がRになるようなものが存在することである．
抽象トポロジカルグラフ(G,R)が弱実現可能であるとは，Gのトポロジカル描画で，その描画における交差辺対の集合がRの部分集合になるものが存在することである．
抽象トポロジカルグラフ(G,R)が単実現可能であるとは，Gのトポロジカル描画で，その描画における交差辺対の集合がRであり，なおかつ，各辺対の交差回数が高々1になるようなものが存在することである．
抽象トポロジカルグラフ(G,R)が直線実現可能であるとは，Gの直線描画で，その描画における交差辺対の集合がRになるようなものが存在することである．
抽象トポロジカルグラフの実現可能性と弱実現可能性については既に研究があり，一連の研究でその判定問題がどちらもNP完全であることが示されている (もっとも難しい部分はNPに所属することを示す部分であり，intersection graph theoryの分野の最近の結果として最も華々しいものだと認識されている)．
この論文では単実現可能性と弱単実現可能性がNP完全で，弱直線実現可能性がNP困難であることが示されている．
また，グラフが完全グラフであるとき，実現可能性，弱実現可能性，弱単実現可能性がNP完全で，弱直線実現可能性がNP困難であるのに対して，単実現可能性が多項式時間で解けることを示している．
弱直線実現可能性がNPに属するかどうかは未解決．

Efficient Extraction of Multiple Kuratowski Subdivisions

M. Chimani, P. Mutzel, and J.M. Schmidt

いわゆるKuratowskiの定理とは，グラフが平面的であるための必要十分条件は
それがK5の細分もK3,3の細分も含まないことである，と主張するものである．
Hopcroft-Tarjanの平面性判定アルゴリズムは線形時間で走るが，与えられたグラフが平面的でないときにその証拠を与えるわけではない (いわゆるcertifying algorithmではない)．
一方，Boyer-Myrvoldのアルゴリズムは線形時間で走り，与えられたグラフが平面的でないときにその証拠 (つまり，K5かK3,3の細分) を与える．
この論文では，与えられたグラフが平面的でないときにその証拠をたくさん与える線形時間アルゴリズムを与えている．

話 (とその後の質疑応答) を聞いた限りでは，全ての証拠を見つけるわけではないようなので，全てをうまく見つけるようなアルゴリズムが構築できたらうれしいかもしれない．

Cover Contact Graphs

N. Atienza, N. de Castro, C. Cortes, M.A. Garrido, C. Grima, G. Hernandez, A. Marquez, A. Moreno, M. Nollenburg, J.R. Portillo, P. Reyes, J. Valenzuela, M.T. Villar, and A. Wolff

著者が14人もいるなんて，アルゴリズムの理論の論文としては異例．

平面上に点集合Sが与えられて，Sの各点pに対してそれを含むような円盤c(s)を考える．
そのような円盤全体の集合の接触グラフとして表わされる平面的グラフはどのようなものだろうか?という問いを考えた論文 (Sをseedと呼ぶことにする)．
まず，任意のSに対して，Sをseedとする連結平面グラフが存在する．
次に，与えられた平面グラフG=(V,E)と点集合Sに対して，SをseedとするGの描画があるかどうか判定する問題はNP完全である．
その他，Sの点が1直線上にある場合や，seedが点集合ではなくて円の集合である場合も考察している．

Matched Drawings of Planar Graphs

E. Di Giacomo, W. Didimo, M. van Kreveld, G. Liotta, and B. Speckmann

2つの平面的グラフG1=(V1,E1)とG2=(V2,E2)，および，頂点集合の全単射φ:V1→V2が与えられたとき，すべてのv1∈V1に対してv1のｙ座標とφ(v1)のｙ座標が同一であるようなG1とG2の描画をmatched drawingということにする．
この論文では，matched drawableでない平面的グラフと木の組が存在すること，および，任意の2つの木は必ずmatched drawableであることが証明されている．
Complexityは未解決．他にも任意の平面的グラフとmatched drawableな平面的グラフの特徴づけが未解決．

Maximum Upward Planar Subgraphs of Embedded Planar Digraphs

C. Binucci, W. Didimo, and F. Giordano

有向グラフが上向き平面的であるとは，すべての有向辺が下から上に向かうように辺交差なくそのグラフが描画できることである．
この論文では，グラフの頂点の位置が予め指定されているときに，辺数最大の上向き平面的部分グラフを求める問題を考えている (どうして頂点の位置を固定するかというと，そうしないと，先行研究から問題のNP困難性が直ちに得られてしまうからである)．
まず，この問題がNP困難であることを証明して，その後でヒューリスティクスなどを提案している．

Minimizing the Area of Planar Straight-Line Grid Drawings

M. Krug and D. Wagner

辺を直線として，頂点を整数格子点上に埋め込む描画で面積が最小のものを求める問題について，それがNP困難であることを示し (3-partitionによる)，与えられた描画の面積を削減するヒューリスティクスを提案している．
実用的な厳密アルゴリズムがないようで，そういうものがあったらよいと発表で言及されていた．

On Planar Polyline Drawings

H. Zhang and S. Sadasivam

面積(p+1)×(n-2)の平面描画で，bendの総数が高々p，各辺のbend数が高々1であるようなものが存在することを示している．
ただし，p=(2n-5)/3．
面積最適な平面描画も先行研究で知られているが，その描画ではbendの総数がもっと大きくなってしまう．
発表では，(2n-2)/3×(2n-2)/3の面積でbend総数が高々(2n-5)/3になるような描画が得られることも言及されていた (これは面積最適でもある)．

Large-Scale Graphics: Digital Nature and Laser Projection

N. Chiba

招待講演2．

前半は自然現象を再現するグラフィクスにおいてどのように計算量を削減しながら見劣りしない図を計算するか議論．
後半は落ちてしまった．Non-photorealistic renderingと関係があったようだ．

Constrained Stress Majorization Using Diagonally Scaled Gradient Projection

T. Dwyer and K. Marriott

頂点同士が離れていないといけないというseparation constraintを持つstress最小化問題をどのようにして解くか，という論文．
問題自体は線形制約付き凸2次計画になるが，問題の構造を活かし係数行列の対角要素のみをスケーリングすることで高速に解が得られることを示している．
話の後で個人的に質問してみたところ，理論的にも１次収束が保証されるようである．

Line Crossing Minimization on Metro Maps

M.A. Bekos, M. Kaufmann, K. Potika, and A. Symvonis

鉄道路線図を少ない交差で描く問題．
先行研究Benkert et al. の立場を踏襲して，考えるグラフをパスと木に一般化．
問題設定が若干複雑なので，ここではこれ以上の説明を省略．

Algorithms for Multi-Criteria One-Sided Boundary Labeling

M. Benkert, H. Haverkort, M. Kroll, and M. Nollenburg

以前紹介した論文 (http://d.hatena.ne.jp/okamoto7/20070426参照) の続き．
動的計画法を用いて，より一般的な枠組に対してアルゴリズムを提案している．
これによって，先行研究の未解決問題を解決している．

Multi-Circular Layout of Micro/Macro Graphs

M. Baur and U. Brandes

ミクロ構造とマクロ構造の両方を併せ持つグラフの描画．
マクロ構造は普通に描画することにして，ミクロ構造については，各マクロノードの中をcircular layoutにして，
マクロノードとマクロノードをつなぐ部分はBachmaier ('07) のradial layoutを用いている．