ファーリの定理

グラフ理論の数学分野において、ファーリの定理は、任意の単純な平面グラフは、交差なしに、その辺が直線セグメントとなるように描画できると述べています。つまり、グラフの辺を直線セグメントではなく曲線として描画できるようになったとしても、描画できるグラフの種類が増えるわけではありません。この定理はイシュトヴァーン・ファーリにちなんで名付けられましたが、クラウス・ワーグナー（1936年）、ファーリ（1948年）、シャーマン・K・スタイン（1951年）によってそれぞれ独立に証明されました。   

ファーリーの定理を証明する一つの方法は、数学的帰納法を用いることである。^{[ 1 ]} G をn個の頂点を持つ 単純平面グラフとする 。必要に応じて辺を追加して、G を最大平面グラフとすることができる。n < 3 の場合、結果は自明である。n ≥ 3 の場合、平面性を維持しながら辺の数が多い任意の面に辺を追加できるため、Gのすべての面は三角形でなければならない。これは 最大平面性の仮定に矛盾する。Gの三角形面を形成する3 つの頂点a、b、cを選択する。nに関する帰納法によって、三角形abcが埋め込みの外側面となる、Gの直線的な組み合わせ的に同型な再埋め込みが存在することを証明する。 （組み合わせ的に同型であるとは、新しい図の頂点、辺、面を古い図のそれらに対応させることができ、頂点と辺の間だけでなく、辺、頂点、面間のすべての接続が保存されることを意味します。）基本ケースとして、n = 3でa、b、cがGの唯一の頂点である場合、結果は自明です。したがって、 n ≥ 4と仮定できます。

平面グラフのオイラーの公式によれば、 G は3 n − 6本の辺を持ちます。同様に、Gの頂点vの欠損を6 − deg ( v )と定義すると、欠損の合計は12になります。Gは少なくとも 4 つの頂点を持ち、Gのすべての面は三角形であるため、 Gのすべての頂点の次数は少なくとも 3 になります。したがって、Gの各頂点の欠損は最大で 3 であり、正の欠損を持つ頂点は少なくとも 4 つあります。特に、a、b、cとは異なる、最大で 5 つの隣接を持つ頂点vを選択できます。Gからv を取り除き、 vを取り除いて形成された面fを再三角形化することによってG' が形成されるとします。帰納法により、G' は組み合わせ的に同型な直線再埋め込みを持ち、その面はabcが外側の面となります。G'の再埋め込みはG'と組み合わせ論的に同型であるため、 G' を作成するために追加された辺を取り除くと、面f が残ります。これは、最大で 5 つの辺を持つ多角形Pです。直線上の組み合わせ論的に同型なGの再埋め込みの描画を完了するには、v を多角形内に配置し、直線で多角形の頂点に接続する必要があります。アートギャラリー定理により、 vからPの頂点への辺が他のどの辺とも交差しないようにvを配置できるPの内部の点が存在し、証明が完了します。

この証明における帰納的段階は右図に示されている。

ド・フレイセ、パッハ、ポラックは、グラフのサイズに比例する次元を持つグリッド内で直線描画を線形時間で見つける方法を示し、 2乗サイズの普遍的な点集合を与えた。シュナイダーも同様の方法を用いて、境界の拡張と、接続半順序に基づく平面性の特徴付けを証明した。彼の研究は、最大平面グラフのエッジをシュナイダーウッドとして知られる3つの木に分割する特定の分割の存在を強調した。

タッテのバネ定理は、3連結平面グラフはすべて、交差のない平面上に描画でき、その辺は直線セグメントで、外側の面は凸多角形になるという定理である（タッテ 1963）。この定理は、グラフの辺を表すバネのシステムの平衡位置として、このような埋め込みが見つかることから、このように呼ばれている。

シュタイニッツの定理は、すべての3連結平面グラフは3次元空間の凸多面体の辺として表現できると述べている。${\displaystyle G,}$タットの定理で説明されているタイプのものは、そのような多面体表現を平面に投影することによって形成される可能性がある。

円充填定理とは、平面グラフはすべて、平面上の互いに交差しない円の集合の交差グラフとして表現できるという定理である。グラフの各頂点を対応する円の中心に配置すると、直線で表現できる。

ハイコ・ハーヴォース氏は、すべての平面グラフに、すべての辺の長さが整数となる直線表現が存在するかどうかという疑問を提起した。^{[ 2 ]}ハーヴォース氏の予想の真偽は未だ不明である。3次グラフについては、距離が整数となる直線埋め込みが存在することが知られている。^{[ 3 ]}

サックス（1983）は、 3次元ユークリッド空間にリンクレス埋め込みを持つすべてのグラフが、2次元埋め込みに関するファーリーの定理と同様に、すべてのエッジが直線セグメントで表されるリンクレス埋め込みを持つかどうかという問題を提起した。

• 曲がりの最小化

• Fáry、István (1948)、「平面グラフの直線表現について」、Acta Sci.数学。 (セゲド)、11 : 229–233、MR 0026311 。
• de Fraysseix, Hubert; Pach, János ; Pollack, Richard (1988)、「平面グラフのFary埋め込みをサポートする小さな集合」、第20回ACM理論計算機科学シンポジウム、pp. 426–433、doi : 10.1145/62212.62254、ISBN  0-89791-264-0S2CID 15230919​ 。
• de Fraysseix, Hubert; Pach, János ; Pollack, Richard (1990)、「グリッド上に平面グラフを描く方法」、Combinatorica、10 : 41–51、doi : 10.1007/BF02122694、MR 1075065、S2CID 6861762  。
• Geelen, Jim ; Guo, Anjie; McKinnon, David (2008)、「整数辺長を持つ立方体平面グラフの直線埋め込み」(PDF)、Journal of Graph Theory、58 (3): 270–274、doi : 10.1002/jgt.20304。
• ヘイコ、ハーバース。ケムニッツ、アーンフリート。メラー、マインハルト。 Süssenbach、Andreas (1987)、「Ganzzahlige planare Darstellungen der platonischen Körper」、Elemente der Mathematik、42 (5): 118–122、MR 0905393 。
• Kemnitz, A.; Harborth, H. (2001)、「平面グラフの平面積分描画」、Discrete Mathematics、236 ( 1–3 ): 191–195、doi : 10.1016/S0012-365X(00)00442-8。
• モハール、ボヤン（2003）、『曲面上のグラフ』からの抜粋問題集。
• Mohar, Bojan ; Thomassen, Carsten (2001), Graphs on Surfaces , Johns Hopkins University Press, pp.  roblem 2.8.15, ISBN 0-8018-6689-8。
• Sachs, Horst (1983)、「平面グラフにおけるクラトフスキーの定理の空間的類似性について ― 未解決問題」、Horowiecki, M.、Kennedy, JW、Sysło, MM (編)、『グラフ理論：1981年2月10日～13日にポーランドのワグフで開催された会議の議事録』、Lecture Notes in Mathematics、第 1018巻、Springer-Verlag、pp. 230–241、doi : 10.1007/BFb0071633、ISBN  978-3-540-12687-4。
• Schnyder, Walter (1990)、「平面グラフのグリッドへの埋め込み」、第1回ACM/SIAM離散アルゴリズムシンポジウム（SODA）論文集、応用数理学会、pp. 138–148、ISBN  9780898712513。
• Stein, SK (1951)、「凸マップ」、アメリカ数学会紀要、2 (3): 464–466、doi : 10.2307/2031777、JSTOR 2031777、MR 0041425  。
• Tutte, WT (1963)、「グラフの描き方」、ロンドン数学会紀要、13 : 743–767、Bibcode : 1963PLMS...13..743T、doi : 10.1112/plms/s3-13.1.743、MR 0158387 。
• ワーグナー、クラウス( 1936)、「Bemerkungen zum Vierfarbenproblem」、Jahresbericht der Deutschen Mathematiker-Vereinigung、46 : 26–32。