幾何グラフ理論

広義の幾何グラフ理論は、グラフ理論の大規模で不定形のサブフィールドであり、幾何学的手段によって定義されるグラフに関係しています。より厳密な意味では、幾何グラフ理論は、ユークリッド平面に描かれ、交差する可能性のある直線のエッジを持つグラフ、およびエッジが頂点を接続する任意の連続曲線であることが許される位相グラフの、組み合わせ的および幾何学的特性を研究します。したがって、これは「幾何学的および位相的グラフの理論」と説明できます (Pach 2013)。幾何グラフは、空間ネットワークとしても知られています。

平面直線グラフは、頂点がユークリッド平面上の点として埋め込まれ、辺が交差しない線分として埋め込まれたグラフです。ファリーの定理によれば、任意の平面グラフは平面直線グラフとして表すことができます。三角形分割は、それ以上辺を追加することができない平面直線グラフで、すべての面が必ず三角形になるためこのように呼ばれます。特殊なケースとしてドロネー三角形分割があり、これは、2 点だけを含む円が存在する場合は常に、2 点を辺で結ぶことによって平面上の点の集合から定義されるグラフです。

多面体または多面体の1 次元スケルトンは、その多面体または多面体の頂点と辺の集合です。任意の凸多面体のスケルトンは平面グラフであり、任意のk次元凸多面体のスケルトンはk連結グラフです。逆に、シュタイニッツの定理によれば、任意の 3 連結平面グラフは凸多面体のスケルトンです。このため、このクラスのグラフは多面体グラフとも呼ばれます。

ユークリッドグラフは、頂点が平面上の点を表し、各辺の長さがその端点間のユークリッド距離に等しいグラフです。ユークリッド最小全域木は、ユークリッド完全グラフの最小全域木です。距離の条件によってグラフを定義することもできます。特に、単位距離グラフは、平面上で単位距離離れた点のペアを接続することによって形成されます。ハドヴィガー・ネルソン問題は、これらのグラフの彩色数に関するものです。

交差グラフは、各頂点が集合に関連付けられ、対応する集合が空でない交差を持つ場合は常に頂点が辺で接続されているグラフです。集合が幾何学的オブジェクトである場合、結果は幾何学的グラフです。たとえば、1 次元の線分の交差グラフは区間グラフです。平面内の単位円の交差グラフは単位円グラフです。円充填定理は、交差しない円の交差グラフがまさに平面グラフであると述べています。シャイネルマンの予想(2009 年に証明) は、すべての平面グラフは平面内の線分の交差グラフとして表すことができると述べています。

点と線の族のレヴィ グラフには、これらのオブジェクトごとに頂点があり、すべての点と線のペアごとに辺があります。射影構成のレヴィ グラフは、多くの重要な対称グラフとケージにつながります。

閉じた多角形の可視グラフは、頂点を結ぶ線分が完全に多角形内にある場合は常に、各頂点のペアをエッジで接続します。無向グラフを可視グラフとして表現できるかどうかを効率的にテストする方法はわかっていません。

部分立方体は、グラフ内の距離が対応する超立方体の頂点間のハミング距離に等しくなるように頂点を超立方体の頂点に関連付けることができるグラフです。グラフの非巡回方向や超平面配置における領域間の隣接性など、多くの重要な組み合わせ構造の族は、部分立方体グラフとして表すことができます。部分立方体の重要な特殊なケースは、パーミュトヘドロン (permutohedron)のスケルトンです。パーミュトヘドロンとは、頂点が順序付けられたオブジェクトのセットの順列を表し、辺が順序が隣接するオブジェクトのスワップを表すグラフです。メディアン グラフを含む他のいくつかの重要なグラフ クラスには、メトリック埋め込みを含む関連定義があります (Bandelt & Chepoi 2008)。

フリップグラフは、点集合の三角形分割から形成されるグラフです。各頂点は三角形分割を表し、2 つの三角形分割は、一方の辺をもう一方の辺に置き換えることによって異なる場合は、辺によって接続されます。四辺形または擬似三角形への分割や、高次元の三角形分割に対して、関連するフリップ グラフを定義することもできます。凸多角形の三角形分割のフリップ グラフは、アソシアヘドロンまたはスタシェフ多面体のスケルトンを形成します。点集合の通常の三角形分割(高次元の凸包の投影) のフリップ グラフは、いわゆる二次多面体のスケルトンとして表すこともできます。

• 位相グラフ理論
• 化学グラフ
• 空間ネットワーク

• Bandelt, Hans-Jürgen; Chepoi, Victor (2008)。「計量グラフ理論と幾何学: 概観」(PDF)。離散幾何学と計算幾何学に関する概観 - 20 年後。現代数学。第 453 巻。アメリカ数学会。pp. 49–86。
• Pach, János編 (2004)。『幾何学的グラフの理論に向けて』。現代数学。第342巻。アメリカ数学会。
• パッハ、ヤーノス (2013)。 「幾何グラフ理論の始まり」。エルデシュ 100 周年。ボリャイサッカー数学。スタッド。 Vol. 25. ブダペスト：ヤーノシュ・ボリャイ数学。社会465–484ページ。土井：10.1007/978-3-642-39286-3_17。MR  3203608。
• Pisanski, Tomaž ; Randić, Milan (2000)。「幾何学とグラフ理論の架け橋」。Gorini, CA (編)。Geometry at Work: Papers in Applied Geometry。ワシントン DC: Mathematical Association of America。pp. 174–194。2007-09-27 にオリジナルからアーカイブ。

• ウィキメディア・コモンズの幾何学的グラフ理論に関連するメディア