Loading article…
位相グラフ理論において、1 平面グラフとは、各辺が最大で 1 つの交差点を持ち、その交差点で 1 つの追加辺と交差するようにユークリッド平面に描画できるグラフです。平面グラフの最も自然な一般化の 1 つである 1 平面グラフがそのように描画された場合、その描画は1 平面グラフまたはグラフの 1 平面埋め込みと呼ばれます。
着色
1-平面グラフは、Ringel (1965) によって初めて研究され、最大 7 色で着色できることが示されました。 [1]その後、これらのグラフを着色するために必要な色の正確な数は、最悪の場合でも 6 であることが示されました。[2] 1-平面である完全グラフ K 6の例は、1-平面グラフに 6 色が必要な場合があることを示しています。ただし、6 色で常に十分であることの証明はより複雑です。
リンゲルの動機は、平面グラフの全彩色のバリエーションを解決しようとすることであった。このバリエーションでは、平面グラフの頂点と面を同時に彩色し、隣接する 2 つの頂点が同じ色にならないようにし、隣接する 2 つの面が同じ色にならないようにし、互いに隣接する頂点と面が同じ色にならないようにする。これは、 2 つの互いに素な 4 色セットを使用して、与えられたグラフとその双対グラフに別々に4 色定理を適用することで、8色を使用して明らかに実行できる。しかし、与えられた平面グラフの各頂点または面に対して頂点を持ち、2 つの補助グラフ頂点が与えられた平面グラフの隣接する特徴に対応するときは常に隣接する補助グラフを形成することで、より少ない色を得ることができる。補助グラフの頂点彩色は、元の平面グラフの頂点面彩色に対応する。この補助グラフは 1 平面であるため、リンゲルの頂点面彩色問題は 6 色でも解決できることがわかる。[2]グラフK6はこのように補助グラフとして形成することはできませんが、頂点面彩色問題では6色が必要になることもあります。例えば、彩色する平面グラフが三角柱である場合、その11個の頂点と面には6色が必要です。なぜなら、そのうちの3つに単一の色を割り当てることはできないからです。[3]
エッジ密度
n個の頂点を持つすべての 1 平面グラフは、最大で 4 n − 8 個の辺を持ちます。[4]さらに強いて言えば、各 1 平面描画には最大でn − 2 個の交差があります。交差する辺のペアから 1 本の辺を削除すると、最大で 3 n − 6 個の辺を持つことができる平面グラフが残り、そこから 元の 1 平面グラフの辺の数の 4 n − 8 の境界が直ちに導かれます。 [5] ただし、平面グラフ (与えられた頂点セット上のすべての最大平面グラフは互いに同じ数の辺を持ちます) とは異なり、 4 n − 8 個よりも大幅に少ない辺を持つ最大1 平面グラフ (1 平面性を維持しながら追加の辺を追加できないグラフ) が存在します 。[6] 1平面グラフの最大辺数4n −8の境界は、 7頂点の完全グラフK7が1平面ではないことを示すために使用できる。このグラフには21の辺があり、この場合4n −8 = 20 < 21であるためである。[7]
1 平面グラフは、ちょうど 4 n − 8 本の辺（最大数）を持つ場合、最適 1 平面グラフと呼ばれます。最適 1 平面グラフの 1 平面埋め込みでは、交差していない辺は必然的に四角形分割（すべての面が四辺形である多面体グラフ）を形成します。すべての四角形分割は、2 つの対角線を各四辺形の面に追加することで、このようにして最適 1 平面グラフを生み出します。したがって、すべての最適 1 平面グラフはオイラーグラフ（すべての頂点の次数が偶数）であり、そのようなグラフの最小次数は 6 であり、すべての最適 1 平面グラフには次数がちょうど 6 の頂点が少なくとも 8 つあります。さらに、すべての最適 1 平面グラフは4 頂点接続であり、そのようなグラフのすべての 4 頂点カットは、基になる四角形分割の分離サイクルです。[8]
直線の1平面描画（つまり、各辺が線分で表され、各線分が最大1つの辺と交差する描画）を持つグラフでは、辺の最大数は4n−9とわずかに厳しく制限され、 これは無限個のグラフによって達成される。[9]
完全な多部グラフ
1 平面完全グラフ、完全二部グラフ、およびより一般的には完全多部グラフの完全な分類が知られています。形式K 2, nのすべての完全二部グラフは1 平面 (偶数平面) であり、形式K 1,1, nのすべての完全三部グラフも同様です。これらの無限の例セット以外では、完全な多部 1 平面グラフは、 K 6、K 1,1,1,6、K 1,1,2,3、K 2,2,2,2、K 1,1,1,2,2 、およびそれらのサブグラフのみです。最小の非 1 平面完全多部グラフは、 K 3,7、K 4,5、K 1,3,4、K 2,3,3、およびK 1,1,1,1,3です。例えば、完全二部グラフK 3,6はK 1,1,1,6のサブグラフなので1平面であるが、K 3,7は1平面ではない。[7]
計算の複雑さ
与えられたグラフが1平面であるかどうかをテストすることはNP完全であり、 [10] [11]平面グラフに1つの辺を追加して形成されたグラフや、制限された帯域幅のグラフに対してもNP完全のままです。[12]この問題は、循環数または木の深さでパラメータ化されている場合は固定パラメータで扱いやすいため、これらのパラメータが制限されている場合は多項式時間で解くことができます。[13]
平面グラフに対するファリの定理とは対照的に、すべての 1 平面グラフを、その辺に直線セグメントを使用して 1 平面的に描画できるわけではない。 [14] [15]ただし、1 平面描画をこのように直線化できるかどうかをテストすることは、多項式時間で実行できる。[16]さらに、3 頂点で連結されたすべての1 平面グラフには、描画の外側の面にある最大 1 つの辺に曲がりがある 1 平面描画がある。この描画は、グラフの 1 平面埋め込みから線形時間で構築できる。 [17] 1 平面グラフには、制限された本の厚さ があるが、[18] K 2,2,2,2を含む一部の 1 平面グラフでは、本の厚さが少なくとも 4 である。[19]
1-平面グラフは、局所的な木幅が限られている。つまり、直径dの 1-平面グラフの木幅が最大でf ( d ) となるような (線形) 関数fが存在する。より一般的には、1 辺あたりの交差数が限られている、種数が限られている表面に埋め込むことができるグラフにも、同じ特性が当てはまる。また、グラフにはセパレータと呼ばれる小さな頂点の集合があり、これを削除すると、グラフは全体のサイズの一定の割合で接続されたコンポーネントに分解される。これらの特性に基づいて、ベイカーの近似アルゴリズム設計手法など、平面グラフのさまざまなアルゴリズムを 1-平面グラフに拡張できる。たとえば、この方法は、 1-平面グラフの最大独立集合に対する多項式時間の近似スキームにつながる。[20]
一般化と関連概念
1-平面性に対する外平面グラフに類似したグラフのクラスは、外 1-平面グラフと呼ばれます。これらは、円板内に描画できるグラフで、頂点は円板の境界上にあり、1 辺あたりの交差は最大でも 1 つです。これらのグラフは、常に (外 1-平面的な方法で) 直線の辺と直角の交差で描画できます。[21]与えられたグラフのSPQR 木に対して動的計画法を使用することで、それが外 1-平面であるかどうかを線形時間でテストできます。[22] [23]グラフの 3 連結成分 (SPQR 木のノード) は、サイクル グラフ、結合グラフ、および 4 頂点の完全グラフのみで構成できます。このことから、外 1-平面グラフは平面であり、木幅は最大でも 3であることがわかります。
1平面グラフには4マップグラフが含まれる。これは平面上の領域の隣接関係から形成されるグラフで、最大4つの領域が任意の点で出会う。逆に、すべての最適な1平面グラフは4マップグラフである。ただし、最適な1平面ではない1平面グラフはマップグラフではない可能性がある。[24]
1 平面グラフはk平面グラフに一般化されており、各辺が最大でk回交差するグラフです(0 平面グラフはまさに平面グラフです)。Ringel は、Gの局所交差数を、G がk平面描画を持つような最小の非負整数kと定義しました。局所交差数は最適な描画の辺の交差グラフの最大次数であり、厚さ(辺を分割できる平面グラフの最小数) は適切な描画の交差グラフの彩色数と見なすことができるため、ブルックスの定理から、厚さは最大で 1 プラス局所交差数であることが分かります。[25] n頂点のk平面グラフには最大でO ( k 1/2 n ) 辺があり、[26]ツリー幅はO (( kn ) 1/2 ) です。[27]深さdのk平面グラフの浅いマイナーは、それ自体が(2d + 1) k平面グラフであるため、1平面グラフの浅いマイナーとk平面グラフもスパースグラフであり、1平面グラフとk平面グラフは有界な展開を持つことを意味します。[28]
非平面グラフは、交差数、つまりグラフの描画時に交差する辺のペアの最小数によってパラメータ化されることもあります。交差数がkのグラフは必ずk平面ですが、その逆は必ずしも当てはまりません。たとえば、Heawood グラフの交差数は 3 ですが、3 つの交差がすべてグラフの同じ辺で発生する必要はないため、1 平面であり、実際には交差の総数と辺ごとの交差数を同時に最適化する方法で描画できます。
非平面グラフに関連するもう 1 つの概念は、グラフを平面にするために削除する必要があるエッジの最小数である グラフの歪度です。
参考文献
- ^ Ringel、Gerhard (1965)、「Ein Sechsfarbenproblem auf der Kugel」、Abhandlungen aus dem Mathematischen セミナー der Universität Hamburg (ドイツ語)、29 (1–2): 107–117、doi :10.1007/BF02996313、MR 0187232、S2CID 123286264。
- ^ ab Borodin, OV (1984)、「平面グラフの頂点面彩色と 1 平面グラフの彩色に関するリンゲル問題の解決」、Metody Diskretnogo Analiza (41): 12–26, 108, MR 0832128。
- ^ Albertson, Michael O.; Mohar, Bojan (2006)、「局所平面グラフの頂点と面の色付け」(PDF)、Graphs and Combinatorics、22 (3): 289–295、doi :10.1007/s00373-006-0653-4、MR 2264852、S2CID 1028234。
- ^ Schumacher, H. (1986)、「Zur Struktur 1-planarer Graphen」、Mathematische Nachrichten (ドイツ語)、125 : 291–300、doi :10.1002/mana.19861250122、MR 0847368。
- ^ チャップ、ユリウス; Hudák、Dávid (2013)、「1 平面グラフの描画と分解について」、Electronic Journal of Combinatorics、20 (2)、P54、doi : 10.37236/2392。
- ^ ブランデンブルク、フランツ・ヨーゼフ;デヴィッド・エップスタイン;グライスナー、アンドレアス。マイケル・T・グッドリッチ;ハナウアー、キャスリン。 Reislhuber、Josef (2013)、「最大 1 平面グラフの密度について」、Didimo、Walter にて。パトリニャーニ、マウリツィオ編（編）、Ｐｒｏｃ．第20回国際症状グラフ描画。
- ^ ab Czap, Július; Hudák, Dávid (2012)、「完全多部グラフの 1 平面性」、離散応用数学、160 (4–5): 505–512、doi :10.1016/j.dam.2011.11.014、MR 2876333。
- ^ 鈴木 雄介 (2010)、「最大 1 平面グラフの再埋め込み」、SIAM Journal on Discrete Mathematics、24 (4): 1527–1540、doi :10.1137/090746835、MR 2746706。
- ^ ディディモ、ウォルター（2013）、「直線1平面グラフ描画の密度」、情報処理レター、113（7）：236–240、doi：10.1016/j.ipl.2013.01.013、MR 3017985。
- ^ Grigoriev, Alexander; Bodlaender, Hans L. (2007)、「辺あたりの交差が少ない埋め込み可能なグラフのアルゴリズム」、Algorithmica、49 (1): 1–11、doi :10.1007/s00453-007-0010-x、hdl : 1874/ 17980 、MR 2344391、S2CID 8174422。
- ^ Korzhik, Vladimir P.; Mohar, Bojan (2009)、「1-immersions の最小障害と 1-planarity テストの難しさ」、Tollis, Ioannis G.; Patrignani, Maurizio (編)、Graph Drawing: 16th International Symposium, GD 2008、Heraklion, Crete, Greece、2008 年 9 月 21 ～ 24 日、改訂版論文、Lecture Notes in Computer Science、vol. 5417、Springer、pp. 302 ～ 312、arXiv : 1110.4881、doi :10.1007/978-3-642-00219-9_29、ISBN 978-3-642-00218-2、S2CID 13436158。
- ^ Cabello, Sergio; Mohar, Bojan (2012)、平面グラフに 1 辺を追加すると交差数と 1 平面性が困難になる、arXiv : 1203.5944、Bibcode :2012arXiv1203.5944C2010 年の第 17 回 ACM 計算幾何学シンポジウムの論文の拡張版。
- ^ ab Bannister, Michael J.; Cabello, Sergio; Eppstein, David (2013)、「1-平面性のパラメータ化された複雑さ」、アルゴリズムとデータ構造シンポジウム (WADS 2013)、第 22 巻、pp. 23–49、arXiv : 1304.5591、Bibcode :2013arXiv1304.5591B、doi :10.7155/jgaa.00457、S2CID 4417962。
- ^ エグルトン、ロジャー B. (1986)、「グラフの直線描画」、Utilitas Mathematica、29 :149–172、MR 0846198。
- ^ Thomassen, Carsten (1988)、「グラフの直線描画」、Journal of Graph Theory、12 (3): 335–341、doi :10.1002/jgt.3190120306、MR 0956195。
- ^ Hong, Seok-Hee ; Eades, Peter ; Liotta, Giuseppe ; Poon, Sheung-Hung (2012)、「1 平面グラフの Fáry の定理」、Gudmundsson, Joachim、Mestre, Julián、Viglas, Taso (編)、Computing and Combinatorics: 18th Annual International Conference、COCOON 2012、シドニー、オーストラリア、2012 年 8 月 20 ～ 22 日、議事録、Lecture Notes in Computer Science、vol. 7434、Springer、pp. 335 ～ 346、doi :10.1007/978-3-642-32241-9_29、ISBN 978-3-642-32240-2。
- ^ Alam, Md. Jawaherul; Brandenburg, Franz J.; Kobourov, Stephen G. (2013)、「3接続1平面グラフの直線グリッド描画」、グラフ描画：第21回国際シンポジウム、GD 2013、フランス、ボルドー、2013年9月23日〜25日、改訂選択論文（PDF）、Lecture Notes in Computer Science、vol. 8242、pp. 83–94、doi：10.1007/978-3-319-03841-4_8、ISBN 978-3-319-03840-7。
- ^ Bekos, Michael A.; Bruckdorfer, Till; Kaufmann, Michael; Raftopoulou, Chrysanthi (2015)、「1-Planar graphs have constant book thick」、Algorithms – ESA 2015、Lecture Notes in Computer Science、vol. 9294、Springer、pp. 130–141、doi :10.1007/978-3-662-48350-3_12、ISBN 978-3-662-48349-7。
- ^ Bekos, Michael; Kaufmann, Michael; Zielke, Christian (2015)、「SAT 解決の観点から見た本の埋め込み問題」、Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015)、pp. 113–125。
- ^ Grigoriev & Bodlaender (2007)。Grigoriev と Bodlaender は、既知の 1 平面埋め込みを持つグラフについてのみ結果を述べ、交差を次数 4 の頂点に置き換えた埋め込みの平面化のツリー分解を使用しています。ただし、彼らの方法は、元の 1 平面グラフの制限されたローカル ツリー幅を直接示唆するため、埋め込みを知らなくても Baker の方法を直接適用できます。
- ^ Dehkordi, Hooman Reisi; Eades, Peter (2012)、「すべての外側 1 平面グラフには直角交差図がある」、International Journal of Computational Geometry & Applications、22 (6): 543–557、doi :10.1142/S021819591250015X、MR 3042921。
- ^ Hong, Seok-Hee ; Eades, Peter ; Katoh, Naoki ; Liotta, Giuseppe ; Schweitzer, Pascal ; Suzuki, Yusuke (2013)、「A linear-time algorithm for testing outer-1-planarity」、Wismath, Stephen、Wolff, Alexander (eds.)、第 21 回国際シンポジウム、GD 2013、フランス、ボルドー、2013 年 9 月 23 ～ 25 日、改訂選書、Lecture Notes in Computer Science、vol. 8242、pp. 71 ～ 82、doi : 10.1007/978-3-319-03841-4_7、ISBN 978-3-319-03840-7。
- ^ クリストファー・アウアー;バックマイヤー、クリスチャン。ブランデンブルク、フランツ J.グライスナー、アンドレアス。ハナウアー、キャスリン。ニューワース、ダニエル。 Reislhuber、Josef (2013)、「線形時間における外側 1 平面グラフの認識」、Wismath、Stephen; Wolff, Alexander (編)、第 21 回国際シンポジウム、GD 2013、ボルドー、フランス、2013 年 9 月 23 ～ 25 日、改訂された厳選論文、コンピュータ サイエンスの講義ノート、vol. 8242、pp. 107–118、土井: 10.1007/978-3-319-03841-4_10、ISBN 978-3-319-03840-7。
- ^ 陳志中;グリニ、ミケランジェロ。Papadimitriou、Christos H. (2002)、「マップ グラフ」、Journal of the ACM、49 (2): 127–138、arXiv : cs/9910013、doi :10.1145/506147.506148、MR 2147819、S2CID 2657838。
- ^ カイネン、ポール(1973)、「グラフの厚さと粗さ」、Abh. Math. Sem. Univ. Hamburg、39 : 88–95、doi :10.1007/BF02992822、MR 0335322、S2CID 121667358。
- ^ Pach, János ; Tóth, Géza (1997)、「辺あたりの交差が少ないグラフ」、Combinatorica、17 (3): 427–439、doi :10.1007/BF01215922、MR 1606052、S2CID 20480170。
- ^ Dujmović, Vida ; Eppstein, David ; Wood, David R. (2015)、「属、ツリー幅、および局所交差数」、Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015)、pp. 77–88、arXiv : 1506.04380、Bibcode :2015arXiv150604380D。
- ^ Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012)、Sparsity: Graphs, Structures, and Algorithms、Algorithms and Combinatorics、vol. 28、Springer、Theorem 14.4、p. 321、doi :10.1007/978-3-642-27875-4、ISBN 978-3-642-27874-7、MR 2920058。