傾斜数

グラフ描画および幾何学的グラフ理論において、グラフの傾き数とは、頂点がユークリッド平面上の点として表され、辺が非接続頂点を通らない線分として表されるグラフの描画における辺の異なる傾きの最小数である。

完全なグラフ

離散幾何学における密接に関連する問題は、スコット (1970) やジェイミソン (1984) などによって以前に研究されていましたが、グラフの傾き数を決定する問題は、ウェイドとチュー (1994) によって導入され、 $n$ 頂点の完全グラフ $K n$ の傾き数はちょうど $n$ であることが示されました。この傾き数を持つ図は、グラフの頂点を正多角形上に配置することによって形成できます。

学位との関係

$最大次数d$ のグラフの傾き数は明らかに少なくともです。これは、次数 $d の$ 頂点に入射する辺のうち、傾きを共有できるのは最大でも 2 つだからです。より正確には、傾き数は少なくともグラフの線形樹木度に等しくなります。これは、単一の傾きの辺は線形フォレストを形成する必要があり、線形樹木度は少なくともであるためです。 $\lceil d/2\rceil$ $\lceil d/2\rceil$

数学における未解決の問題:

最大次数 4 のグラフには、制限された傾き数がありますか?

（数学における未解決の問題がさらに増える）

最大次数5 で任意の大きな傾き数を持つグラフが存在する。 ^[1]しかし、最大次数 3 のグラフはすべて傾き数が最大で 4 である。^{[2]完全グラフ} $K 4$ に対する Wade & Chu (1994) の結果は、これが厳密であることを示している。 4 つの傾きのあらゆるセットがすべての次数 3 のグラフを描くのに適しているわけではない。傾きのセットがこの目的に適しているのは、それが平行四辺形の辺と対角線の傾きを形成する場合のみである。特に、任意の次数 3 のグラフは、その辺が軸に平行であるか、整数格子の主対角線に平行になるように描くことができる。^[3]最大次数 4 のグラフの傾き数が有界か無界かはわかっていない。^[4]

平面グラフ

Keszegh、Pach、Pálvölgyi (2011) が示したように、すべての平面グラフには平面直線描画があり、その中で異なる傾斜の数はグラフの次数の関数である。彼らの証明は、次数の関数として平面グラフの角度解像度を制限する Malitz と Papakostas (1994) の構成に従っており、次数を定数倍以上増やさずにグラフを最大平面グラフに完成させ、円充填定理を適用してこの拡張グラフを接円の集合として表す。初期グラフの次数が制限されている場合、充填における隣接する円の半径の比も環補題[ ^5]によって制限されます。これは、4 分木を使用して各グラフ頂点をその円内の点に配置すると、小さな整数の比である傾斜が生成されることを意味します。この構成によって生成される異なる傾斜の数は、グラフの次数に対して指数関数的です。

複雑

グラフの傾きが2であるかどうかを判断することはNP完全です。 ^{[6]このことから、任意のグラフの傾きの数を決定すること、または3/2よりも良い}近似比で傾きを近似することはNP困難であることがわかります。

平面グラフに傾きが2の平面描画があるかどうかを判断することもNP完全であり、^[7]実数の存在理論では平面描画の傾きの最小値を判断することは困難である。 ^[8]

注記

^ Barát、Matoušek & Wood (2006) と Pach & Pálvölgyi (2006) によって独立に証明され、Dujmović、Suderman & Wood (2005) によって提起された問題を解きました。Pach & Sharir (2009) の定理 5.1 と 5.2 を参照してください。
^ Mukkamala & Szegedy (2009)、Keszegh らの初期の結果を改良。 (2008); Pach & Sharir (2009) の定理 5.3。
^ ムッカマラとパルヴェルジ (2012)。
^ パック＆シャリル（2009年）。
^ ハンセン（1988年）。
^ フォーマンら。 (1993);イーズ、ホン＆プーン (2010);マシュクら。（2011年）。
^ ガーグ＆タマシア（2001年）。
^ ホフマン (2016).

参考文献

Barát, János; Matoušek, Jiří ; Wood, David R. (2006)、「有界次数グラフは任意に大きな幾何学的厚みを持つ」、Electronic Journal of Combinatorics、13 (1): R3、MR 2200531。
Dujmović, Vida ; Suderman, Matthew; Wood, David R. (2005)、「Really straight graph drawings」、Pach, János (ed.)、Graph Drawing: 12th International Symposium、GD 2004、ニューヨーク、NY、USA、2004 年 9 月 29 日～10 月 2 日、Revised Selected Papers、Lecture Notes in Computer Science、vol. 3383、ベルリン: Springer-Verlag、pp. 122～132、arXiv : cs/0405112、doi :10.1007/978-3-540-31843-9_14。
Eades, Peter ; Hong, Seok-Hee ; Poon, Sheung-Hung (2010)、「グラフの直線描画について」、Eppstein, David ; Gansner, Emden R. (編)、『グラフ描画: 第 17 回国際シンポジウム、GD 2009、シカゴ、イリノイ州、米国、2009 年 9 月 22 ～ 25 日、改訂版論文』、Lecture Notes in Computer Science、vol. 5849、ベルリン: Springer、pp. 232 ～ 243、doi : 10.1007/978-3-642-11805-0_23、MR 2680455。
Formann, M.; Hagerup, T.; Haralambides, J.; Kaufmann, M.; Leighton, FT ; Symvonis, A.; Welzl, E. ; Woeginger, G. (1993)、「高解像度での平面グラフの描画」、SIAM Journal on Computing、22 (5): 1035–1052、doi :10.1137/0222063、MR 1237161。
Garg, Ashim; Tamassia, Roberto (2001)、「上向きおよび直線平面性テストの計算複雑性について」、SIAM Journal on Computing、31 (2): 601–625、doi :10.1137/S0097539794277123、MR 1861292。
ハンセン、ローウェル J. (1988)、「ロダンとサリバンの環の補題について」、複素変数、理論と応用、10 (1): 23–30、doi :10.1080/17476938808814284、MR 0946096。
ホフマン、ウド (2016)、「平面傾斜数」、第 28 回カナダ計算幾何学会議 (CCCG 2016) の議事録。
ジェイミソン、ロバート E. (1984)、「いくつかの傾斜を決定する平面構成」、Geometriae Dedicata、16 (1): 17–34、doi :10.1007/BF00147419、MR 0757792。
ケシェグ、バラズ。Pach, ヤーノス; Pálvölgyi、Dömötör (2011)、「傾斜がほとんどない境界次数の平面グラフの描画」、Brandes、Ulrik ; Cornelsen、Sabine (編)、Graph Drawing: 18th International Symposium、GD 2010、コンスタンツ、ドイツ、2010 年 9 月 21 ～ 24 日、改訂された厳選論文、コンピュータサイエンスの講義ノート、vol. 6502、ハイデルベルク: Springer、pp. 293–304、arXiv : 1009.1315、doi :10.1007/978-3-642-18469-7_27、MR 2781274。
ケシェグ、バラズ。Pach, ヤーノス;パルヴェルジ、ドメトル; Tóth, Géza (2008)、「最大 5 つの傾斜を備えた立方体グラフの描画」、Computational Geometry: Theory and Applications、40 (2): 138–147、doi : 10.1016/j.comgeo.2007.05.003、MR 2400539。
マリッツ、セス; パパコスタス、アキレアス (1994)、「平面グラフの角度分解能について」、SIAM Journal on Discrete Mathematics、7 (2): 172–183、doi :10.1137/S0895480193242931、MR 1271989。
Maňuch, Ján; Patterson, Murray; Poon, Sheung-Hung; Thachuk, Chris (2011)、「グラフの非平面直線描画の複雑さ」、Brandes, Ulrik ; Cornelsen, Sabine (編)、『グラフ描画: 第 18 回国際シンポジウム、GD 2010、コンスタンツ、ドイツ、2010 年 9 月 21 ～ 24 日、改訂選書』、Lecture Notes in Computer Science、vol. 6502、ハイデルベルク: Springer、pp. 305 ～ 316、doi :10.1007/978-3-642-18469-7_28、hdl : 10281/217381、MR 2781275。
Mukkamala, Padmini; Szegedy, Mario (2009)、「4方向の立方体グラフの幾何学的表現」、計算幾何学：理論と応用、42 (9): 842–851、doi：10.1016/j.comgeo.2009.01.005、MR 2543806。
Mukkamala, Padmini; Pálvölgyi, Dömötör (2012)、「4 つの基本傾斜を持つ立方グラフの描画」、van Kreveld, Marc; Speckmann, Bettina (編)、『グラフ描画: 第 19 回国際シンポジウム、GD 2011、オランダ、アイントホーフェン、2011 年 9 月 21 ～ 23 日』、改訂選択論文、Lecture Notes in Computer Science、vol. 7034、Springer、pp. 254 ～ 265、arXiv : 1106.1973、doi :10.1007/978-3-642-25878-7_25。
Pach, ヤーノス; Pálvölgyi、Dömötör (2006)、「有界次数グラフは任意の大きな傾き数を持つことができる」、Electronic Journal of Combinatorics、13 (1): N1、MR 2200545。
Pach, János ; Sharir, Micha (2009)、「5.5 角度分解能と傾斜」、組み合わせ幾何学とそのアルゴリズム的応用: アルカラ講義、数学的概説とモノグラフ、第 152 巻、アメリカ数学会、pp. 126–127。
$スコット、PR（1970）、「 n$ 点によって決定される方向の集合について」、アメリカ数学月刊誌、77：502-505、doi：10.2307/2317384、MR 0262933。
ウェイド、GA; チュー、J.-H. (1994)、「最小傾斜セットを使用した完全グラフの描画可能性」、コンピュータジャーナル、37 (2): 139–142、doi : 10.1093/comjnl/37.2.139。

[1] Barát、Matoušek & Wood (2006) と Pach & Pálvölgyi (2006) によって独立に証明され、Dujmović、Suderman & Wood (2005) によって提起された問題を解きました。Pach & Sharir (2009) の定理 5.1 と 5.2 を参照してください。

[2] Mukkamala & Szegedy (2009)、Keszegh らの初期の結果を改良。 (2008); Pach & Sharir (2009) の定理 5.3。

[3] ムッカマラとパルヴェルジ (2012)。

[4] パック＆シャリル（2009年）。

[5] ハンセン（1988年）。

[6] フォーマンら。 (1993);イーズ、ホン＆プーン (2010);マシュクら。（2011年）。

[7] ガーグ＆タマシア（2001年）。

[8] ホフマン (2016).