凸描画

グラフ描画において、平面グラフの凸描画とは、グラフの頂点をユークリッド平面の点として、辺を直線セグメントとして表し、描画のすべての面 (外面を含む) が凸境界を持つような描画である。面の境界は、グラフの頂点の 1 つを曲がることなくまっすぐ通過することがある。厳密に凸な描画では、さらに面の境界が各頂点で曲がることが求められる。つまり、厳密に凸な描画では、グラフの各頂点は、各入射面の形状を記述する各凸多角形の頂点でもある。

すべての多面体グラフには厳密に凸な描画があり、^[1]たとえば、グラフを表す凸多面体のシュレーゲル図として得られます。これらのグラフでは、凸 (ただし必ずしも厳密に凸である必要はありません) 描画は、各辺の長さがグラフの頂点の数に比例するグリッド内で線形時間で見つけることができます。^[2]^[3]ただし、厳密に凸な描画にはより大きなグリッドが必要になる場合があります。たとえば、1 つの面に線形の頂点数があるピラミッドなどの多面体の場合、そのグラフの厳密に凸な描画には立方面積のグリッドが必要です。 ^[4]線形時間アルゴリズムは、各辺の長さが 2 乗であるグリッド内で多面体グラフの厳密に凸な描画を見つけることができます。^[5]

多面体でない他のグラフも、凸描画、または厳密に凸描画を持つことができます。完全な二部グラフなどの一部のグラフは、凸描画を持ちますが、厳密に凸描画ではありません。凸描画を持つグラフの組み合わせ的特徴付けは既知であり、^[6]線形時間で認識できますが、^[7]描画に必要なグリッド次元と、これらのグラフの小さな凸グリッド描画を構築するための効率的なアルゴリズムは、すべてのケースで既知ではありません。^[8] $K_{2,3}$

凸描画は、各頂点が隣接する頂点の凸包内に収まる必要がある凸埋め込みとは区別される。凸埋め込みは2次元以外の次元にも存在でき、グラフが平面である必要はなく、平面グラフの平面埋め込みであっても必ずしも外面が凸である必要はない。^[9]

参考文献

^ Tutte, WT (1960)、「グラフの凸表現」、ロンドン数学会紀要、第3シリーズ、10 : 304–320、doi :10.1112/plms/s3-10.1.304、MR 0114774
^ Kant, G. (1996)、「標準順序付けを使用した平面グラフの描画」、Algorithmica、16 (1): 4–32、doi :10.1007/s004539900035、hdl : 1874/16676、MR 1394492
^ ボニション、ニコラス; フェルスナー、ステファン; モスバ、モハメド (2007)、「3連結平面グラフの凸描画」、アルゴリズミカ、47 (4): 399–420、doi :10.1007/s00453-006-0177-6、MR 2304987、S2CID 375595
^ アンドリュース、ジョージ E. (1963)、「多数の境界格子点を持つ厳密に凸な体の体積の下限」、アメリカ数学会誌、106 (2): 270–279、doi : 10.2307/1993769、JSTOR 1993769、MR 0143105
^ イムレ、バラニ; Rote, Günter (2006)、「平面グラフの厳密な凸面描画」、Documenta Mathematica、11 : 369–391、arXiv : cs/0507030、doi :10.4171/dm/214、MR 2262937、S2CID 47071207
^ Thomassen, Carsten (1980)、「有限グラフと無限グラフの平面性と双対性」、Journal of Combinatorial Theory、シリーズ B、29 (2): 244–271、doi : 10.1016/0095-8956(80)90083-0、MR 0586436
^ 千葉則重、山内正、西関隆夫 (1984)、「平面グラフの凸描画のための線形アルゴリズム」、Bondy, J. Adrian、Murty, USR (編)、Progress in graph theory (Waterloo, Ont., 1982)、Academic Press、pp. 153–173、MR 0776799
^ 周暁; 西関隆雄 (2010)、「グリッド上の内部三連結平面グラフの凸描画」、離散数学、アルゴリズムおよびアプリケーション、2 (3): 347–362、doi :10.1142/S179383091000070X、MR 2728831 $O(n^{2})$
^ Linial, N. ; Lovász, L. ; Wigderson, A. (1988)、「ゴムバンド、凸埋め込み、グラフ接続」、Combinatorica、8 (1): 91–102、doi :10.1007/BF02122557、MR 0951998、S2CID 6164458

[tutte-1] Tutte, WT (1960)、「グラフの凸表現」、ロンドン数学会紀要、第3シリーズ、10 : 304–320、doi :10.1112/plms/s3-10.1.304、MR 0114774

[kant-2] Kant, G. (1996)、「標準順序付けを使用した平面グラフの描画」、Algorithmica、16 (1): 4–32、doi :10.1007/s004539900035、hdl : 1874/16676、MR 1394492

[bfm-3] ボニション、ニコラス; フェルスナー、ステファン; モスバ、モハメド (2007)、「3連結平面グラフの凸描画」、アルゴリズミカ、47 (4): 399–420、doi :10.1007/s00453-006-0177-6、MR 2304987、S2CID 375595

[andrews-4] アンドリュース、ジョージ E. (1963)、「多数の境界格子点を持つ厳密に凸な体の体積の下限」、アメリカ数学会誌、106 (2): 270–279、doi : 10.2307/1993769、JSTOR 1993769、MR 0143105

[br-5] イムレ、バラニ; Rote, Günter (2006)、「平面グラフの厳密な凸面描画」、Documenta Mathematica、11 : 369–391、arXiv : cs/0507030、doi :10.4171/dm/214、MR 2262937、S2CID 47071207

[thomassen-6] Thomassen, Carsten (1980)、「有限グラフと無限グラフの平面性と双対性」、Journal of Combinatorial Theory、シリーズ B、29 (2): 244–271、doi : 10.1016/0095-8956(80)90083-0、MR 0586436

[cyn-7] 千葉則重、山内正、西関隆夫 (1984)、「平面グラフの凸描画のための線形アルゴリズム」、Bondy, J. Adrian、Murty, USR (編)、Progress in graph theory (Waterloo, Ont., 1982)、Academic Press、pp. 153–173、MR 0776799

[zn-8] 周暁; 西関隆雄 (2010)、「グリッド上の内部三連結平面グラフの凸描画」、離散数学、アルゴリズムおよびアプリケーション、2 (3): 347–362、doi :10.1142/S179383091000070X、MR 2728831 $O(n^{2})$

[llw-9] Linial, N. ; Lovász, L. ; Wigderson, A. (1988)、「ゴムバンド、凸埋め込み、グラフ接続」、Combinatorica、8 (1): 91–102、doi :10.1007/BF02122557、MR 0951998、S2CID 6164458