Graph Drawing 1日目
Graph Drawingは会議録が会議の後に発行されて，会議中に論文を読むことができないので，細かいところをこの報告で書くことができません．お許し下さい．
今日のメニュー．
Crossing Number of Graphs with Rotation Systems
M.J. Pelsmajer, M. Schaefer and D. Stefankovic
各点に接続する辺がその点の周りでどのような順番に出現するかを与えた埋め込みにおける交差数の計算に関する話．
まず，一般にはNP困難．この結果によって，他の人の様々な結果の証明が簡潔になった．
そして，頂点数が1の場合 (頂点数が1でもループ同士が交差することに注意)，O(nlogn)時間アルゴリズム，頂点数が2の場合多項式時間で計算できることを示している．
頂点数が3以上の定数の場合は未解決．
A Bipartite Strengthening of the Crossing Lemma
J. Fox, J. Pach and C. D. Toth
交差数定理の対交差数バージョンは多くの辺と交差する辺の存在を示しているが，ここではそのような辺がたくさん存在し，それらが完全2部グラフのような交差パターンを持つことを示している．
すなわち，disjointな辺部分集合で片方の辺がもう一方の全ての辺と交差するようなものが存在し，その辺部分集合もある程度の大きさを持っているというのである．
ただし，任意の2辺の交差する回数は定数で抑えられていないといけない．
Improvement on the Decay of Crossing Numbers
J. Cerny, J. Kyncl, and G. Toth
任意のグラフGには，小さな部分グラフでその交差数がGの交差数の定数倍になるものが存在することをFox and Tothは証明したが，この論文では定数を改善 (ほとんど1) にしている．
Crossing Numbers and Parameterized Complexity
M.J. Pelsmajer, M. Schaefer and D. Stefankovic
奇交差数がkのグラフを考える．そのようなグラフを奇交差数がkになるように平面に埋め込むとき，交差数を9^k以下にできることを示している．
この結果から （直ちにではないが)，奇交差数や対交差数の計算がFPTであることが分かる．
Characterization of Unlabeled Level Planar Graphs
J.J. Fowler and S.G. Kobourov
頂点にラベルがついていて，そのラベルにしたがって頂点を縦方向に並べなければいけない描画を考える．
そのような描画で辺交差のないものが存在する場合，グラフとラベル付けの対をlevel planarと言う．
どのようなラベル付けに対してもlevel planarになるグラフをunlabeled level planarと言う．
この論文ではunlabeled level planarグラフを禁止部分グラフによって特徴づけている．
Cyclic Level Planarity Testing and Embedding
C. Bachmaier, W. Brunner and C. Konig
先と同様にlevel planarityを考えているが，一番上と一番下がサイクリックにつながっている場合を考えている．
そのように埋め込めるグラフとラベル付けの対をcyclic level planarと呼ぶことにし，cyclic level planarグラフかどうかをO(nlogn)時間で判定するアルゴリズムを与えている．
Practical Level Planarity Testing and Layout with Embedding Constraints
M. Harrigan and P. Healy
Level planarityを判定する既知の線形時間アルゴリズムはPQ-treeを使っているので，実装が難しい (そうだ)．
この論文では，vertex-exchangeグラフというものを使って，2乗の計算量で判定とlevel planarである場合にそのような描画を求めるアルゴリズムを与えている．
Minimum Level Nonplanar Patterns for Trees
J.J. Fowler and S.G. Kobourov
木がlevel planarであるかどうかを判定するアルゴリズムを与えている．
そのために，既知の2つの最小禁止パターンに加えて2つの最小禁止パターンを発見し，それらがlevel planarな木を特徴付けていることを証明している．
Computing Symmetries of Combinatorial Objects
B.D. McKay
招待講演．
グラフ，行列，ラテン方陣，線形符号の対称性を議論．
行列，ラテン方陣の対称性はグラフの問題に(多項式時間で)帰着できるが，線形符号の対称性の問題がそうできるかどうかは大きな未解決問題のようだ．
ただし，線形符号は生成行列で与えられているとする．
そして，McKayの開発したnautyに関する説明も行なわれた．
Straight-Line Orthogonal Drawings of Binary and Ternary Trees
F. Frati
頂点数nの二分木や三分木を描画する話だけど，描画において各辺は水平か鉛直に描く場合 (orthogonal)，各頂点の子供が左から右へ並ぶ順番が決まっている場合 (order-preserving) を考察している．
結果として，二分木のorthogonal order-preserving描画として面積がO(n^1.5)のもの，三分木のorthogonal描画として面積がO(n^1.631)のもの，完全三分木のorthogonal描画として面積がO(n^1.262)のものを得ている．これらの面積について，下界はΩ(n)なのでまだギャップがある．
Polynomial Area Bounds for MST Embeddings of Trees
M. Kaufmann
与えられた木を最小費用全域木として持つ平面上の点集合があるかどうかという問題について議論．
最大次数が７の場合にはそのような点集合が存在しないが，5以下なら必ず存在するということが知られている．
最大次数が6の場合は，その存在性判定がNP困難．
問題は最大次数が5以下の場合の描画面積で，既存の結果は木の高さがkのときに面積が2^(k^2)×2^(k^2)であった．
この論文では，最大次数が3，4の場合に面積をkの多項式で抑えることに成功している．
最大次数が5のときにどうなるかは未解決だけど，発表者は指数関数的になるのではないかと言っていた．
Moving Vertices to Make Drawings Plane
X. Goaoc, J. Kratochvil, Y. Okamoto, C.-S. Shin, and A. Wolff
自分の発表．いつも通り笑いとかは取れるけども，テクニカルにあんまり伝わったかどうか微妙．そもそもNP困難性の証明を発表しようとしたのがいけなかったかもしれないけど．
最近だんだん発表が下手になっている気がするから，ちゃんと発表練習するように心がけたい．
Point-Set Embedding of Trees with Edges Constraints
E. Di Giacomo, W. Didimo, G. Liotta, H. Meijer, and S. Wismath
平面上に与えられた点集合を頂点集合とするように与えられた平面グラフが埋め込めるか，という問題 (いわゆるpoint-set embeddability)．
その変種として，平面グラフの一部分も既に埋め込まれている場合を考えた論文．特に木の場合を考察している．
結果として，n-k個の辺がk-3個のbendを持ってしまうインスタンスが存在することが示されている．
ただし，kは既に埋め込まれた部分の頂点数．
更に，各辺のbendの数をおよそk+1に抑えて埋め込むことが常に可能であることも示している．
つまり，bendの数に関して下界がk-3，上界がk+1になっているわけで，そのギャップを埋めることがopen problemになっている．
