数理解析研究所講究録
第 1799 巻 2012 年 191-194191

単位円交差グラフの線形構造を持つ部分クラスについて
林貴 史 *

木野 徹 *

桑原 勇人 *

長澤 亮介 *

芝田 悠華 *

山崎 浩一 *\dagger

1

はじめにを $G$ 上での $u,$

diam $(G)$ を$G$$v$間の最短経路の辺数とする．また，の直径とし $\max_{u,v\in}vdist_{G}(u,v)$ で定

単位円交差グラフとはグラフの各頂点を直径の等で表す．
義する． の最大独立集合のサイズをしい円で表した交差グラフで，アドホックヮイヤレスあるグラフが単位円交差グラフ (以降，単に単位円$G$ネットワークなどに応用を持っ [1,2,3]. 本稿では単$\alpha(G)$グラフと記す) とは，2 次元平面上において各頂点が位円交差グラフを単に単位円グラフと呼ぶことにす 直径 1 の (閉じた)円に対応し，二つの円が重なりをる．単位円グラフは自然なグラフクラスでもあるた持つ場合のみ，対応する 2 頂点間に辺を持つグラフ
め，様々な研究結果が得られている．例えば入カグラ のことである．連結な単位円グラフ全体からなる集フを単位円グラフに制限しても，独立頂点集合問題， 合を UDG で表す．あるグラフが単位区間グラフと彩色問題，支配集合問題は NP 困難であることが知 は，各頂点が長さ 1 の閉区間に対応し，二つの区間がられている [4]. また，単位円グラフの認識問題は NP重なりを持つ場合のみ，対応する 2 頂点間に辺をもつ困難である [3]. 単位円グラフを表現するのに必要なグラフのことである．連結な単位区間グラフ全体か領域はその単位円グラフの直径から制限を受けるた
め，重なりを持たない円の配置数には限界がある．限らなる集合を UIG で表す．便宜上しばしば，UIG をで表す (UIG は UDG のサブクラで，UDG をられた領域内に如何に多く重なりを持たない円を配 スであることに注意).
置できるかという円パッキング問題も盛んに研究さ$R=\{p_{i}=(x_{i}, y_{i})|x_{i}, y_{i}\in\Re, 1\leq i\leq n\}$ が$L_{0}$れている (cf. [5]).

$L_{\infty}$

単位円グラフ $G=(V=(v_{1}, \ldots,v_{n}), E)$ の中心点表

ある限られた領域内で表現可能な単位円グラフが現とは，$\sqrt{(x_{i}-x_{j})^{2}+(y_{i}-y_{j})^{2}}\leq 1$ iff
らなる集合 (つまりグラフクラス) に対する研究も行$E(1\leq i<j\leq n)$ が成り立つ時をいう．ここで各われている [6]. 縦 4, 横無限長の矩形内で表現可能にはが対応する． は単位円の中心点を表し，な単位円グラフ全体からなる集合は co-comparabihty
は単位円に対応する頂点を表すが，本稿ではこれら二グラフからなる集合に真に含まれることが知られてっを同一視する．なお，本稿を通して P. はある単位$\{p_{i},p_{j}\}\in$$p_{i}$$v_{i}$いる [6]. これにより縦 $L32$ の制限を受けた単位円グ

ラフにおいては，いくつかの NP 完全な問題が線形時$p_{i}$$v_{i}$

円の中心点を，. は単位円に対応する頂点を表すも
$v$

$|$

$\max|x_{i}-x_{j}|,$ $\max|y_{i}-yj|$ をそれぞれのとする．

$R$間で解くことができる．しがし，縦が一 未満で制限 の長さ，幅と呼び $l(R),w(R)$ で表す．
$\sqrt{}$$1$

された単位円グラフの研究は (著者等が知る限り) なされていない．本稿では，縦が$\frac{\sqrt{3}}{2}$未満で制限した場

合に，グラフクラスがどのように変化するがにつぃて中心点表現 $R,$$7ffi$$|$$R$$\lrcorner$の研究する．

$p_{i},pj$

グラフ$(V, E)$に対して，幅 の中心点表現を持つ連結ラフ全体の集合をは縦で表す．したがって$*$$\dagger$$\delta$の長さ $1+\delta$ , 横の長さで表す． および$G$$u,$ $v\inV$

群馬大学$\infty$$|$

に対し，$dist_{G}(u, v)$ であり，UIG

本研究は科研費 (21500004) の助成を受けたものである．

$L_{\delta}$の矩形内に単位円を配置して得られる連結な単位円グラフ全体からなる集合$($を頂点集合 $V$ , 辺集合 $E$ を用いて $G=$$Pj$で定義し，diam $(R)$ で表す．

$L_{\delta}$

準備$G$に対して $Pi,$(ユークリッド) 距離を $dist_{R}(p_{i},p_{j})$ で表す．の直径を $R$ 上の最も離れた 2 頂点間の距離$\forall\delta(\delta\geq 0)$

2$R$の$\max_{p_{l},p\inR}jdist_{R}(p_{i,Pj})$
1$\grave\grave$$\in$$=L_{0}\subseteq L_{\delta}\subseteq L_{\infty}=UDG$が成り立つ．

あるグラフが比較可能グラフ (comparability192graph) とは，半順序中で互いに比較可能な要素を辺で結んだグラフのことである．比較可能グラフの補グラフを $cx$ comparabilityグラフという． 撃は
co-comparability グラフからなる集合に真に含まれることが知られている [6]. co-comparability 性を保$L$れた領域内に重ならないように配置できる円の個数が diam $(G)$ に依には上限がある．したがって，$\alpha(G)$存した定数で上から抑えられることになる．

補題 2. グラフ $G\in L_{W},$$r\frac{diam(G)}{\sqrt{1-W}}\rceil$$W< \frac{\sqrt{3}}{2}$ならば $\alpha(G)\leq$である．

つという意味では， という値は限界値である．実際でのに対しては，co-comparability グ 証明． を$\mathscr{Q}_{2}$$c>c_{2}3$のある中心点表現とする．補題 1 よ$w(R)\leq W$ ,り diam $(R)\leq diam(G)$ である．よって，$l(R)\leq diam(G)$ である．ここで縦の長さ $W$ , 対角$T$ の横の長さ線の長さが 1 の矩形領域 を考える．
$R$$L_{c}$

ラフ以外のグラフ 例えば$($$C_{k},$$k\geq 6)$を含む．

本研究では以下の問題について考える．

$G$

$T$

問題 1 次を満たす定数 $C$ は存在するか．すなわち$\forall\epsilon(0<\epsilon<C)$に対し，$L_{\epsilon}=L_{c}$.

問題 2 次を満たす定数 $C$ は存在するか．すなわち

に対し，$L_{\epsilon}=L_{c}$$\forall\epsilon(\epsilon>C)$.

$\forall\epsilon(\epsilon>0)$$L_{\epsilon}$と区間グラフも比較不能であいない．また，る (例えば $K_{1,7}$ と$C_{4}$は高々$r\frac{dlam(G)}{\sqrt{1-W}}\rceil$補題 2 より

$L_{\epsilon}$

よって， は chque-width に対してバウンドされて$\bigcap_{0<\epsilon}L_{\epsilon}$$r_{1}^{dia}\ovalbox{\tt\small REJECT}_{-}^{mG}\rceil$

個の独立頂点 (中心点) しか含むことはできないので，$\alpha(G)$UIG は clique-width に対してバウンドされていな一方に対し， は UIG を含む．

い [7].

1 四であるから，個の $T$ で $R$ の領域全てを覆うことができる．しかし，各 $T$ は高々一
は $\psi=$$\neq_{1-W}^{diamG)}+1$である．口$\alpha(G)\leq r_{1-W}^{diamG}\neq\rceil$$\alpha(G)<$である．とすれば，$W>\sqrt{\frac{(\alpha(G)-1)^{2}-diam(G)^{2}}{(\alpha(G)-1)^{l}}}$

したがって次の系を る．本
を $f(G)$ で表す．となる$(’\ovalbox{\tt\small REJECT}$$k^{f}$では，$\sqrt{\frac{(\alpha(G)-1)^{2}-diam(G)^{2}}{(\alpha(G)-1)^{2}}}$).
系 1. グラフ $G\in L_{W},$ $W<L32$ の任意の中心点表現
$R$3

研究結果

3.1

問題 1 について

系 1 より次の定理が成り立つ．
定理 1. 次を満たす定数 $C$ は存在しない．すなわち，我々は問題 1 を否定的に解いた (定理 1). 本節では

定理 1 の証明の概略を与える．そのためにまず補題
1,2 を示す．
補題

1. グラフ$G$の中心点表現$R$について$\forall\epsilon(0<\epsilon<C)$$>$と仮定する． 上$diam(G)$$p_{a},p_{b}$$|p_{a}=u_{0},u_{1},$ $\ldots,u_{k-1},u_{k}=p_{b}]$とすると $\sum_{\dot{l}=0}^{k-1}dist_{R}(u_{i},u_{t+1})\geq dist_{R}(u_{0},u_{k})=$diam $(R)$ である$dist_{R}(uu)$って，$\{u_{j},u_{j+1}\}$が存在するが存在したと仮定する．

$G\in Lc$ ならば
すなわち $\forall\epsilon(0<\epsilon<C)$ に対し，$G\in L_{\epsilon}$である．

を満たすグラフの列 $F_{k}=(G_{1},G_{2}, \ldots,G_{i}, \ldots)$ を考える．

$p_{a},p_{b}$

$G$

$=$

$C$.

$R$とする．すなわち$dist_{R}(p_{a},p_{b})=diam(R)$ である． において

$dist_{R}(p_{a},p_{b})$$L_{\epsilon}=L_{c}$ここで $k$ を 2 以上の整数とし，以下の 3 つの性質の最も離れた 2 頂点をの最短なパスをに対し，証明．条件を満たす定数diam $(R)\leq diam(G)$ .

証明．diam $(R)$に対し $w(R)>f(G)$ が成り立つ．

$\geq$$\frac{d1am(R)}{k}$

したがを満たす辺

さらに，diam $(G)$$\max_{u,v\in V}dist_{G}(u,v)\geq dist_{G}$(uo,$u_{k}$性質 1

性質 2 血窺よって $dist_{R}( uu)\geq\frac{diam(R)}{k}\geq\frac{diam(R)}{diam(G)}>1$ と口

diam$\forall\epsilon’(\epsilon’>0)$$(G_{*}\cdot)=\infty$に対して,$G_{i}$が幅 $f(G_{i})+\epsilon’$ で表

性質 1, 2 より $1\dot{m}_{iarrow\infty}f(G_{i})=0$ である．したがって $f(G_{j})<C$ なる
$C$

なり矛盾

$arrow\infty\infty$に対して $\alpha(G_{i})-diam(G_{i})=k$ ,

性質 3
現可能．

$=$) $=k$ である．

$\forall i(i\geq 1)$

なる$\epsilon’$$G_{j}\in Lc$$G_{j}$が存在する．また，$f(G_{j})+\epsilon’<$は必ず取れる．よって，凡の性質 3 よりである．

しかし系 1 によればの任意の中心点表現 $R$ に
補題 1 により，単位円グラフ
は幅 $f(G_{j})$長さはそれぞれ diam $(G)$ 以下に制限される．制限さ 対し，$w(R)>f(G_{j})$ となる．つまり$G$の中心点表現の幅，$G_{j}$$G_{j}$

193
では表現できない．

$(C>)f(G_{j})\geq\epsilon$

なる$\epsilon$に対して，32となり仮定と矛盾．
性質を全て満たすは確かに存在する．実際，図 1

問題

について

$2$

$G_{j}\not\in L_{\epsilon}$

我々は問題 2 についても否定的に解いた (定理 2).

$F_{k}$

本節では補題 2 の一般化を考え (補題 3), それを用で乃のグラフの例，図 2 でその UDG 表現の例をそれそれ示す．また，図 1 の が性質 3 を満たすこと いて定理 2 を証明する．の証明は割愛する
口補題 3. 縦の長さ , 横の長さ の矩形領域 $D$ 内に，$F_{2}$$l$$w$

重ならないように配置できる単位円の最大個数$\forall h(\frac{1}{2}<h<\mathscr{Q}2)$$I$に対して，$I \leq r\frac{w}{h}\rceil\cross r\frac{l}{\sqrt{1-h^{2}}}\rceil$は，である．

証明．縦の長さ , 対角線の長さ 1 の矩形領域$h$$T$を考える． の横の長さはであるから，個の でを全て覆いきれる．したがって$\sqrt{1-h^{2}}$$T$$r\frac{w}{h}\rceil\cross$

$D$

$T$

$r\frac{l}{\sqrt{1-h^{2}}}\rceil$

鳩ノ巣原理より，$I \leq r\frac{w}{h}\rceil\cross r\frac{l}{\sqrt{1-h}}\rceil$

である．口定理 2. 次を満たす定数 $C$ は存在しない．すなわち，$\forall\epsilon(\epsilon>C)$

に対し，$L_{\epsilon}=L_{c}$.

証明．条件を満たした $C$ が存在すると仮定する．すなわち$\forall\epsilon(\epsilon>C)$に対し，$G\in L_{\epsilon}$

ならば $G\in Lc$ である．

図 1: 乃の例$C$$X\geq C$ なのでに対して $X=\lceil C\rceil$ とする．

である．ここで，図 3 のようなひし形の格子状グラフを考える．明らかに，このようなひし形の$L_{X}\supseteq L_{C}$.

格子状グラフは，UDG に属する．また各 $k=1,2,$$\frac{\wedge\Lambda\Lambda\Lambda\Lambda\Lambda_{\wedge}}{.\backslash \zeta\cross/VV\backslash \gamma^{\backslash }r}$$\ldots$

に対し，頂点数 $2k^{2}-2k+1,$ $diam(H_{k})=2k-2$ ,$\alpha(H_{k})=k^{2}$

なるひし形の格子状グラフ$H_{k}$が存在する．
$H_{k}$のある中心点表現とする．こ$\alpha(H_{k})<8kX$であることを示す．補題 1 よ$H_{k}\in L_{X},$$\frac{-\lambda\lambda\lambda\lambda\lambda_{\wedge}}{.d\backslash ddddd}$.

$R$をのとき，り diam $(R)\leq diam(H_{k})$ であるから，$l(R)\leq 2k-2$である．また $H_{k}\in Lx$ より $w(R)\leq X$ である．
したがって補題 3 を$h= \frac{1}{\sqrt{2}}$として用いれば，$I\leq$となり，よって $I\leq 2w(R)\cross$$2l(R)=4X(2k-2)<8kX$ . したがって，$\lceil\sqrt{2}w(R)\rceil\cross\lceil\sqrt{2}l(R)\rceil$$1$$\alpha(H_{k})\leq$図 2:$F_{2}$の UDG 表現$I<8kX$ .
$J$$\alpha(H_{k})=$
一方 $\alpha(H_{k})=k^{2}$ なので，$k>8X$ に対し，$k^{2}>8kX$ となる．よって $k>8X$ に対し，単位円グ

ラフ$H_{k}$は $L_{X}$ に属さず，したがって$L_{C}$にも属さない．よって矛盾．
$\square$4

今後の課題
今後の課題として以下の 2 つが挙げられる．

194[7] M.C. Golumbic and U. Rotics. On the cliquewidth of some perfect graph classes. Intemational Joumal of Foundations $0 \int Comp$ uter Sci, 2000.
ence, 11 (3)$:423\triangleleft 43$

図 3: グラフ $H$ の概形

1.

$S= \bigcap_{0<\epsilon}L_{\epsilon}$の特徴付け．

2. $\forall a,c(0<a<c)$ に対し，$a<b<c$ が必ず存在するか．

。なる$L_{a}\subsetneq L_{b}\subsetneq L$

参考文献[1] M.L. Huson and A. Sen. Broadcast scheduling algorithm for radio networks. In Military Communications Conference, 1995. MIL$COM’ 95$ , Conference Record, IEEE, volume 2,pages 647-651. IEEE, 1995.

[2] X.Y. Li and Y. Wang. Simple heuristics andptass for intersection graphs in wireless ad hocnetworks. In Proceedings of the 6th international workshop on Discrete algorithms andmethods for mobile compu ting and communications, pages 62-71. ACM, 2002.
[3] H. Breu and D.G. Kirkpatrick. Unit disk graphrmgnition iS NP-h 下 rd Computational Geometry, $9(1-2):3-24$ , 1998.

[4] B.N. Clark, C.J. Colboum, and D.S. Johnson.
Unit disk graphs. Discrete mathematics, $86(1-$3 : 165-177, 1990.
$)$[5] 松井知己．単位円グラフ上の最大独立集合問題の近似解法．情報処理学会研究報告．
$99(26):1-6$ ,1999.
ズム研究会報告，$AL_{l}$アルゴリ[6] H. Breu. Algorithmic aspects of constmined unit
disk gmphs. $PhD$ thesis, University of British

Columbia, 1996.