Graph Drawing 3日目

最終日です．

Constrained Simultaneous and Near-Simultaneous Embeddings

F. Frati, M. Kaufmann, and S. Kobourov

この会議の中でのホットトピックの1つと言えるsimultaneous embedding (同時埋め込み) に関する話．
論文自体はいろんな細かい結果の集合体だけども，例えば，辺を共有しない平面的グラフとパスで，同時幾何埋め込み可能でないものの構成などを与えている．

Simultaneous Geometric Graph Embeddings

A. Estrella-Balderrama, E. Gassner, M. Junger, M. Percan, M. Schaefer, and M. Schulz

与えられた2つの平面的グラフが同時幾何埋め込み可能であるか判定する問題がNP困難であることを示している．
また，この問題がNPに属するならば，直線交差数の計算もNPに属することを示している．
個人的には面白かった．

Efficient C-Planarity Testing for Embedded Flat Clustered Graphs with Small Faces

G. Di Battista and F. Frati

クラスタ化グラフ (clustered graph) とはグラフと頂点集合上のラミナ族の対のことで，クラスタ化平面的 (clustered planar，略してc-planar) グラフとは，グラフとクラスタを平面的に埋め込めるようなもののことである．ここでクラスタを平面的に埋め込めることの定義は，各クラスタを囲む閉ジョルダン曲線があり，それらの曲線同士は交わらず，なおかつ，クラスタに出入りする辺は各曲線と一度しか交わらない，ということとする．
クラスタ化平面的グラフの特徴づけや判定問題がどれくらい難しいのか分かっていないようだけども，この論文ではラミナ族を木で表わしたときに深さが3以下で，グラフ自体の埋め込みが固定されているときにクラスタをうまく描けるかどうか判定するアルゴリズム (そして描ける場合には実際に描く) アルゴリズムを提案している．
問題設定が細かすぎて，分かりにくい．

Clustered Planarity: Small Clusters in Eulerian Graphs

E. Jelinkova, J. Kara, M. Pergel, O. Suchy, and T. Vyskocil

1つ前の論文と同様にc-平面性に関する話．
ここでは，各クラスタの大きさが3以下の場合を考察している．
例えば，それに加えてグラフが3連結の場合にc-平面性の判定が多項式時間でできることを示している．

Drawing Colored Graphs with Constrained Vertex Positions and Few Bends per Edge

E. Di Giacomo, G. Liotta, and F. Trotta

頂点に色が塗られた平面的グラフと，それと同じ数だけ各色の点を持つ平面上の点集合を考えて，グラフの各頂点を同じ色の平面上の頂点に写してグラフ全体を辺交差なく描画できるかどうか考える．
このとき，各辺に必要なbendの数が頂点数に依存してしまうことが知られているが，この論文では使用できる点の数を増やすことで頂点数に依存しないbendの数でグラフが描けることを証明している．
証明の論法が分かりやすかった．

Colorability in Orthogonal Graph Drawing

J. Stola

David Woodが3次元グラフ描画をやっていた頃の未解決問題に任意のk彩色可能グラフが3次元直交直方体描画を持つような最大のkはいくつか?というものがあり，彼自身はその最大値が3と183の間にあることを示していた．
この論文ではそのギャップを「22から42の間」に縮めている．
他にも関連した結果がたくさんあったけども，全然追えなかった (追う気も起きなかったけど)．

A Note on Minimum-Area Straight-Line Drawings of Planar Graphs

F. Frati and M. Patrignani

平面グラフの直線描画の面積の最小値に関する話題．
埋め込みが固定され，頂点数がnのときに面積最小値が最悪n^2のオーダーになると知られているが，それを与える例としてDoley, Leighton, Trickey ('84) の構成したnested triangleというものがある．
この論文ではnested triangleの埋め込みを変えてもよい場合を考えて，埋め込みを変えると面積が半分ぐらい小さくなることを示している．
また，発表の最後ではnested triangleよりも悪い例を示していた．

Universal Sets of n Points for 1-Bend Drawings of Planar Graphs with n Vertices

H. Everett, L. Sylvain, G. Liotta, and S. Wismath

平面上の点集合で，頂点数nの任意の平面的グラフをその点集合の点を頂点として使うことで描けるようなものが存在するかどうか?という問題はグラフ描画の世界の大きな問題で，いろいろと知られていることがある．
まず，辺を全て直線分で描かないといけないというときにはde Fraisseix, Pach, PollackやSchnyderの結果から，点数O(n^2)の集合が存在することが分かっている．一方で，そのような集合の要素数がnになれないことを昔Chrobak and Karloffが示したが，最近Kurowski (IPL '04) が改善している．
辺に高々2つのbendを許すと，任意のn点から成る集合の上で描ける (Kaufmann and Wiese JGAA '02)．
この論文では辺に高々1つしかbendを許さない場合に，あるn点から成る集合が存在して，その上に頂点数nの任意の平面的グラフを描けることを証明している．

LunarVis -- Analytic Visualizations of Large Graphs

R. Gorke, M. Gaertler, and D. Wagner

複雑ネットワークを描画するときに，その解析結果も一緒に描画に組み込む方法を検討．
特に，階層性や相関などを可視化できるように試みた方法を提案している．

Visualizing Internet Evolution on the Autonomous Systems Level

K. Boitmanis, U. Brandes and C. Pich

複雑ネットワークの「全体」を表示し，なおかつ，その進化 (時間発展) も表示するための枠組を提案．

Treemaps for Directed Acyclic Graphs

V. Tsiaras, S. Triantafilou, and I.G. Tollis

いわゆるtreemapを非閉路有向グラフ (DAG) に拡張する試みで，拡張しても全てのDAGがtreemapとして可視化できるわけではなく，与えられたDAGがtreemapとして可視化できるかどうか判定する問題がNP完全であることも示している．

Drawing Graphs with GLEE

L. Nachmanson, G. Robertson, and B. Lee

Microsoftの人々の論文．
開発しているGLEEというライブラリの説明．いわゆるSugiyamaらのアルゴリズムを使っているが，いくつかヒューリスティクスを入れているようだ．

Fingerprints -- Means for Visual Analytics

M. Gaertler, R. Gorke, and D. Wagner

ポスター．
ネットワークの描画に解析結果も含めるanalysis-oriented visualizationの概念を提唱．
上のLunarVisもその一部．

ILOG Diagrammer for .NET

R. Dupuy, E. Durocher, J. Joubert, P. Ruzand, G. Sander, E. Tissandier, and A. Vasiliu

ポスター．ILOGの人々．
ILOGの可視化ツールの紹介．http://www.ilog.com/products/visualization/

The Hierarchical Individual Timestep Method for Large-Scale Graph Drawing

T. Matsubayashi and T. Yamada

ポスター．NTTの人々．
天体物理学で培われた最適化手法を用いてforce-directed法による描画の計算の高速化を行なっている．
いわゆる専用計算機MDGRAPEも用いている．

The Open Graph Drawing Framework

M. Chimani, C. Gutwenger, M. Junger, K. Klein, P. Mutzel, and M. Schulz

ポスター．
著者らの開発しているC++グラフ描画ライブラリOGDFの紹介．http://www.ogdf.net/

www.simultaneousplanarity.net

P. Angelini, P.F. Cortese, F. Frati, M. Patrignani, and M. Rimondini

ポスター．
同時埋め込み可能性に関連してplanarity.netに似たゲームを開発．同時埋め込み可能性の研究に役立てたいそうだ．http://www.simultaneousplanarity.net/

Attribute-Based Visualisation in the New visone

M. Baur, U. Brandes, and D. Wagner

ポスター．
著者らの開発している社会ネットワーク可視化・解析ツールvisoneのバージョンアップで，ノードやリンクに属性を付けることを可能にしたとのこと．http://visone.info/