接触グラフ

グラフ理論の数学の分野において、接触グラフまたは接線グラフは、頂点が幾何学的オブジェクト（曲線、線分、または多角形など）で表され、辺が指定された概念に従って接触している（交差していない）2つのオブジェクトに対応するグラフです。^[1]これは交差グラフの概念に似ていますが、基礎となるオブジェクトが互いに交差できる方法を制限する点で異なります。

円充填定理[ ^2]は、あらゆる平面グラフは円の接触グラフとして表現できると述べています。単位円の接触グラフはペニーグラフと呼ばれます。^[3]三角形、^[4] 長方形、^[5] 正方形、[6]線分、^[ 7 ]^または円弧[ ^8]の接触グラフとしての表現も研究されています。

参考文献

^ Chaplick, Steven; Kobourov, Stephen G.; Ueckerdt, Torsten (2013)、「Equilateral L-contact graphs」、Brandstädt, Andreas、Jansen, Klaus、Reischuk, Rüdiger (eds.)、Graph-Theoretic Concepts in Computer Science - 39th International Workshop、WG 2013、Lübeck、ドイツ、2013 年 6 月 19 ～ 21 日、改訂版論文、Lecture Notes in Computer Science、vol. 8165、Springer、pp. 139 ～ 151、arXiv : 1303.1279、doi :10.1007/978-3-642-45043-3_13、S2CID 13541242
^ Koebe、Paul (1936)、「Kontaktprobleme der Konformen Abbildung」、Ber.ザックス。アカド。ウィス。ライプツィヒ、数学-物理学。 Kl.、88 : 141–164
^ Pisanski, Tomaž ; Randić, Milan (2000)、「Bridges between geometry and graph theory」（PDF）、Gorini, Catherine A.（編）、『Geometry at Work』、MAA Notes、vol. 53、Cambridge University Press、pp. 174–194、MR 1782654、2022-01-19にオリジナル（PDF）からアーカイブ、 2017-02-19に取得特に176ページを参照
^ de Fraysseix, Hubert; Ossona de Mendez, Patrice ; Rosenstiehl, Pierre (1994)、「三角形接触グラフについて」、Combinatorics, Probability and Computing、3 (2): 233–246、doi :10.1017/S0963548300001139、MR 1288442、S2CID 46160405
^ Buchsbaum, Adam L.; Gansner, Emden R.; Procopiuc, Cecilia M.; Venkatasubramanian, Suresh (2008)、「長方形レイアウトとコンタクトグラフ」、ACM Transactions on Algorithms、4 (1): Art. 8、28、arXiv : cs/0611107、doi :10.1145/1328911.1328919、MR 2398588、S2CID 1038771
^ Klawitter, Jonathan; Nöllenburg, Martin; Ueckerdt, Torsten (2015)、「三角形のない長方形の配置の組み合わせ特性と正方形化可能性問題」、グラフ描画とネットワークの視覚化: 第 23 回国際シンポジウム、GD 2015、ロサンゼルス、カリフォルニア州、米国、2015 年 9 月 24 ～ 26 日、改訂選択論文、Lecture Notes in Computer Science、vol. 9411、Springer、pp. 231 ～ 244、arXiv : 1509.00835、doi :10.1007/978-3-319-27261-0_20、S2CID 18477964
^ Hliněný, Petr (2001)、「線分の接触グラフはNP完全である」(PDF)、離散数学、235 (1–3): 95–106、doi : 10.1016/S0012-365X(00)00263-6、MR 1829839
^ Alam, Md. Jawaherul; Eppstein, David ; Kaufmann, Michael; Kobourov, Stephen G.; Pupyrev, Sergey; Schulz, André; Ueckerdt, Torsten (2015)、「円弧の接触グラフ」、アルゴリズムとデータ構造: 第 14 回国際シンポジウム、WADS 2015、ビクトリア、ブリティッシュコロンビア州、カナダ、2015 年 8 月 5 ～ 7 日、議事録、Lecture Notes in Computer Science、vol. 9214、Springer、pp. 1 ～ 13、arXiv : 1501.00318、doi :10.1007/978-3-319-21840-3_1、S2CID 6454732

[ell-1] Chaplick, Steven; Kobourov, Stephen G.; Ueckerdt, Torsten (2013)、「Equilateral L-contact graphs」、Brandstädt, Andreas、Jansen, Klaus、Reischuk, Rüdiger (eds.)、Graph-Theoretic Concepts in Computer Science - 39th International Workshop、WG 2013、Lübeck、ドイツ、2013 年 6 月 19 ～ 21 日、改訂版論文、Lecture Notes in Computer Science、vol. 8165、Springer、pp. 139 ～ 151、arXiv : 1303.1279、doi :10.1007/978-3-642-45043-3_13、S2CID 13541242

[Koebe-2] Koebe、Paul (1936)、「Kontaktprobleme der Konformen Abbildung」、Ber.ザックス。アカド。ウィス。ライプツィヒ、数学-物理学。 Kl.、88 : 141–164

[bridges-3] Pisanski, Tomaž ; Randić, Milan (2000)、「Bridges between geometry and graph theory」（PDF）、Gorini, Catherine A.（編）、『Geometry at Work』、MAA Notes、vol. 53、Cambridge University Press、pp. 174–194、MR 1782654、2022-01-19にオリジナル（PDF）からアーカイブ、 2017-02-19に取得特に176ページを参照

[triangle-4] Fraysseix, Hubert; Ossona de Mendez, Patrice ; Rosenstiehl, Pierre (1994)、「三角形接触グラフについて」、Combinatorics, Probability and Computing、3 (2): 233–246、doi :10.1017/S0963548300001139、MR 1288442、S2CID 46160405

[rectangular-5] Buchsbaum, Adam L.; Gansner, Emden R.; Procopiuc, Cecilia M.; Venkatasubramanian, Suresh (2008)、「長方形レイアウトとコンタクトグラフ」、ACM Transactions on Algorithms、4 (1): Art. 8、28、arXiv : cs/0611107、doi :10.1145/1328911.1328919、MR 2398588、S2CID 1038771

[squarability-6] Klawitter, Jonathan; Nöllenburg, Martin; Ueckerdt, Torsten (2015)、「三角形のない長方形の配置の組み合わせ特性と正方形化可能性問題」、グラフ描画とネットワークの視覚化: 第 23 回国際シンポジウム、GD 2015、ロサンゼルス、カリフォルニア州、米国、2015 年 9 月 24 ～ 26 日、改訂選択論文、Lecture Notes in Computer Science、vol. 9411、Springer、pp. 231 ～ 244、arXiv : 1509.00835、doi :10.1007/978-3-319-27261-0_20、S2CID 18477964

[segments-7] Hliněný, Petr (2001)、「線分の接触グラフはNP完全である」(PDF)、離散数学、235 (1–3): 95–106、doi : 10.1016/S0012-365X(00)00263-6、MR 1829839

[arcs-8] Alam, Md. Jawaherul; Eppstein, David ; Kaufmann, Michael; Kobourov, Stephen G.; Pupyrev, Sergey; Schulz, André; Ueckerdt, Torsten (2015)、「円弧の接触グラフ」、アルゴリズムとデータ構造: 第 14 回国際シンポジウム、WADS 2015、ビクトリア、ブリティッシュコロンビア州、カナダ、2015 年 8 月 5 ～ 7 日、議事録、Lecture Notes in Computer Science、vol. 9214、Springer、pp. 1 ～ 13、arXiv : 1501.00318、doi :10.1007/978-3-319-21840-3_1、S2CID 6454732