ファーリの定理

「ファリーの定理（英語版）」あるいは「ファーリ-ミルナーの定理（英語版）」とは異なります。

ファーリの定理（ファーリのていり、英: Fáry's theorem, 洪: Fáry-tétel）はグラフ理論の定理で、任意の単純平面的グラフについて、その辺を交差しない線分によって描画（英語版）できることを主張する^[1]。ハンガリーの数学者ファーリ・イシュトヴァーンの名を冠する。

Klaus Wagner (1936)、 Fáry (1948)、Sherman K. Stein (1951) によって独立して証明された。定理にヴァーグナーの名を付すこともある。

すべての辺が直線分であるような埋め込みを Fáry embedding という^[2]。また Fáry embedding を持つ平面グラフを直線グラフという^[3]。

証明

ファーリの定理の証明の段階。

ファーリの定理の証明の一つに数学的帰納法を用いるものがある^[4]。n個の頂点を持つ単純平面グラフGを考える。Gが極大となるように必要に応じて辺を加える。n < 3の場合は明らか。n ≥ 3の場合を考える。Gを極大としたのでGのすべての面は三角形である。ある面を選びその頂点をa, b, cとする。nに関する帰納法によって、三角形abcが外領域となる、直線的で組合せ的同型^{[注 1]}である埋め込みの存在を証明する。n = 3のときGの頂点はa, b, cに限られ、Gの求めるべき埋め込みの存在は明らかである。次にn ≥ 4の場合を考える。

オイラーの多面体定理よりGは3n − 6個の辺を持つ。グラフの頂点vの欠損を6 − deg(v) と定義すると、すべての頂点の欠損の和は12となる。Gは少なくとも4つの頂点を持ち、その面はすべて三角形であるので、すべての頂点の次数は3以上である。したがってすべての頂点の欠損は3以下であって、少なくとも4つの頂点が正の欠損を持つ。よってa, b, cでなく、5つ以下の頂点としか繋がっていないある頂点uを選ぶことができる。Gから頂点uを除き、uの除去で出現した面fを三角化したグラフをG′とする。n − 1における先の帰納法の仮定より、G′について三角形abcが外領域となる、直線的で組合せ的同型である埋め込みが存在する。この埋め込みにおいてfの三角化に使用した辺を除去すると、fに対応する面は多くとも5つの辺しか持たない多角形Pとなる。美術館定理（英語版）より、Pの頂点とvを結んだ直線状の辺がPのどの辺とも交わらないような頂点vをP内部に設置することができる。このとき埋め込みのすべての辺は直線であるので、nにおいても命題が成立し、よって任意のnで辺が直線状である埋め込みの存在が確認できる。

関連する結果

de Fraysseix, Pach & Pollack (1990) は、頂点の個数をnとして格子上に線形対数時間O(n log n)で Fáry embedding を描画する方法を示した。この方法でO(n²)の面積の普遍点集合（英語版）を与えることができる。Schnyder (1990) は類似の方法で必要な格子の面積を縮小し、半順序を基にした平面性の特徴づけ（英語版）の一つを証明した。シュナイダーの研究によって、極大な平面的グラフの辺をシュナイダー木（英語版）と呼ばれる3つの木に分割する特定の方法の存在が明示された。

タットのばね定理（英語版）によれば任意の3連結平面的グラフは、その辺が直線状でそれぞれ交差せず、またグラフの外側との境界が凸多角形となるように平面に埋め込むことができる^[5]。この埋め込みではグラフの辺として表されたばねが釣り合うように配置されているため"ばね"定理と呼ばれている。

シュタイニッツの定理（英語版）によれば、任意の3連結平面的グラフは、3次元空間の凸（英語版）多面体によって表現できる。この多面体を平面に投影することによって、タットのばね定理で述べた埋め込みを得ることもできる。

円充填定理は、任意の平面的グラフは平面上で交わらない円の集合の交差グラフ（英語版）として表現できることを述べる。円の中心を結ぶことでグラフの直線的な表現ができる。

Heiko Harborth（ドイツ語版） は、任意の平面的グラフは、すべての辺が直線状であって辺長が整数である埋め込みを持つかという問題を提起した^[6]。Harborthの予想（英語版）と呼ばれるこの問題は未解決のままとなっている。立方体グラフにおいてはそのような埋め込みが存在することが知られている^[7]。

Sachs (1983) は、3次元ユークリッド空間におけるリンクのない埋め込み（英語版）を持つ任意のグラフは、すべての辺が直線状であるリンクのない埋め込みをもつかどうか、という問題を提起した。2次元空間のファーリの定理の類推となっている。