接触グラフ

幾何学的オブジェクト間の接線を表すグラフ

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

円充填定理^[2]は、あらゆる平面グラフはコイングラフとして知られる円の接触グラフとして表現できることを述べています。オデッド・シュラムのモンスター充填定理はこれを一般化します：あらゆる平面グラフは、与えられた任意の滑らかな凸集合の相似コピーの接触グラフです。^[3]単位円の接触グラフはペニーグラフと呼ばれます。^[4]三角形、^[5]長方形、^[6]正方形、^[7]線分、^[8]円弧^[9]の接触グラフとしての表現も研究されています。

参考文献

^ チャップリック, スティーブン; コボロフ, スティーブン G.; ウッカート, トルステン (2013)、「正三角形 L 接触グラフ」、ブランシュテット, アンドレアス; ヤンセン, クラウス; ライシュク, リュディガー (編)、『コンピュータサイエンスにおけるグラフ理論的概念 - 第 39 回国際ワークショップ、WG 2013』、リューベック、ドイツ、2013 年 6 月 19 日～21 日、改訂論文、コンピュータサイエンス講義ノート、第 8165 巻、シュプリンガー、pp. 139～ 151、arXiv : 1303.1279、doi :10.1007/978-3-642-45043-3_13、ISBN 978-3-642-45042-6、S2CID 13541242
^ Koebe、Paul (1936)、「Kontaktprobleme der Konformen Abbildung」、Ber.ザックス。アカド。ウィス。ライプツィヒ、数学-物理学。 Kl.、88 : 141–164
^ Schramm, Oded (1990),規定された組合せ論による2次元体のパッキングと等角写像および準等角写像の構築への応用（博士論文）、プリンストン大学、ProQuest 303827410; 修正され、「Combinatorically Prescribed Packings and Applications to Conformal and Quasiconformal Maps」として再版された、arXiv : 0709.0710、2007年
^ 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年1月19日時点のオリジナル（PDF）からアーカイブ、 2017年2月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、ISBN 978-3-319-27260-3、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、ISBN 978-3-319-21839-7、S2CID 6454732

このグラフ理論関連の記事はスタブです。記事を拡張することでWikipediaに貢献できます。

[ell-1] チャップリック, スティーブン; コボロフ, スティーブン G.; ウッカート, トルステン (2013)、「正三角形 L 接触グラフ」、ブランシュテット, アンドレアス; ヤンセン, クラウス; ライシュク, リュディガー (編)、『コンピュータサイエンスにおけるグラフ理論的概念 - 第 39 回国際ワークショップ、WG 2013』、リューベック、ドイツ、2013 年 6 月 19 日～21 日、改訂論文、コンピュータサイエンス講義ノート、第 8165 巻、シュプリンガー、pp. 139～ 151、arXiv : 1303.1279、doi :10.1007/978-3-642-45043-3_13、ISBN 978-3-642-45042-6、S2CID 13541242

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

[schramm-3] Schramm, Oded (1990),規定された組合せ論による2次元体のパッキングと等角写像および準等角写像の構築への応用（博士論文）、プリンストン大学、ProQuest 303827410; 修正され、「Combinatorically Prescribed Packings and Applications to Conformal and Quasiconformal Maps」として再版された、arXiv : 0709.0710、2007年

[bridges-4] 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年1月19日時点のオリジナル（PDF）からアーカイブ、 2017年2月19日取得特に176ページを参照

[triangle-5] 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-6] 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-7] 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、ISBN 978-3-319-27260-3、S2CID 18477964

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

[arcs-9] 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、ISBN 978-3-319-21839-7、S2CID 6454732