Extension to 3-colorable triangulation
Kenta Ozeki(National Institute of Informatics, Japan)(JST, ERATO, Kawarabayashi Large Graph Project)
Joint work withAtsuhiro Nakamoto (Yokohama National University)
Kenta Noguchi (Tokyo Denki University)

Art Gallery Problem(non-convex) n-gon

Art Gallery Problem :How many guards do we need
to watch everywhere in a museum?

One guard is enoughn/3 guards are enough for any museum with n wall. (Chvatal, `75)
22nd-23rd Dec.

情報系 Winter Festa2

Art Gallery Problem(non-convex) n-gon

Art Gallery Problem :How many guards do we need
to watch everywhere in a museum?

One guard is enoughn/3 guards are enough for any museum with n wall. (Chvatal, `75)
Key idea: Extension to 3-colorable triangulation
22nd-23rd Dec.

情報系 Winter Festa3

Prison Yard Problem
Prison Yard Problem :How many guards do we need
to watch everywhere in a prison?
It has already roomsc.f. Face Cover Problem
Find min. # of vertices hitting all facesNP-hard (Bienstock & Monma, `88)
27-approx. algorithm (Bienstock & Dean, 92)

22nd-23rd Dec.

情報系 Winter Festa4

Prison Yard Problem
Prison Yard Problem :(Reminder) Key idea:
Extension to 3-colorable triangulation

How many guards do we need
to watch everywhere in a prison?

It has already roomsc.f. Face Cover Problem
Find min. # of vertices hitting all facesNP-hard (Bienstock & Monma, `88)
27-approx. algorithm (Bienstock & Dean, 92)

Extension Problem :Determine if a graph can be extended to a 3-colorable tri.
22nd-23rd Dec.

情報系 Winter Festa5

Extension Problem
Extension Problem :Determine if a graph on surface can be extended to a 3-colorable tri.

General plane graphs
NP-complete even for pentagulations(Ext. prob. for pentagulations = 3-coloring prob.)
Quadrangulations (graphs in which all faces are quadlangular)
quad. has an extension to a 3-colorable tri.
-algorithm (Hoffmann & Kriegel, `96)
-algorithm (He & Zhang, `05) + const. delay enumeration
22nd-23rd Dec.

情報系 Winter Festa6

Extension Problem
Mosaics (graphs in which all faces are tri- or quadlangular)
Plane case :PA mosaic G
3-colorable tri
const. delay enumeration= Eulerian tri.
(Hoffmann-Ostenhof + α, `13+)(all vertices have even deg.)
General surface case :3-colorable tri

A mosaic GP

NP-c?

Eulerian tri.
(mod 3)(mod 2)22nd-23rd Dec.

s.t.
情報系 Winter Festa

7

Constant-approximation algorithms forhighly connected multi-dominating sets inunit disk graphs
Takuro Fukunaga

Wireless ad hoc network














hard to keep global information

2/3

Wireless ad hoc network














hard to keep global information ⇒ virtual backbone

2/3k-connected m-dominating set in unit disk graphs
Find a small and stable virtual backbone⇒ k-connected m-dominating set problem in a unit disk graphPrevious results
Constant-approximation algorithms are known only when• k ≤ 3 for uniform weights• k = 1, m = 1 for general weights
Our results
First constant-approximation algorithms
for any (k, m) with a fixed constant k ≤ m3/3

周期グラフ描画の回転対称性について
荒木徹也(NII; Principles of Informatics Research Division Tokyo)
夫紀恵(NII; JST, ERATO, Kawarabayashi Large Graph Project)

問題
周期 グ ラ フ : 結晶格子の組合せ構造を 抽出
静的 グ ラ フ : 無限グラ フ である 周期 グラフを有限データで表現

T EM image of graphenesheet from Multifunctional
polymer nanocomposites,
CRC Press(2010)

6回転対称性を持つ描画

6回転対称性を持たない描画,,

疑問：静的グラフから，対応する周期グラフが並進対称性・回転対称性を持つ描画を持つかどうか判定できるか？

我々の結果Gがコヒーレントであることを仮定する
多くの結晶が満たす性質

Gの全ての描画
並進対称
回転対称
consistent
結果1:この集合が空でない必要条件
結果2:充足判定アルゴリズム

我々の結果Gがコヒーレントであることを仮定する
多くの結晶が満たす性質

Gの全ての描画
並進対称
回転対称
consistent
結果1:この集合が空でない必要条件
結果2:充足判定アルゴリズム

一部の周期グラフについて，回転対称性を持ち得ないことを証明するアルゴリズム