ファーリの定理

ファーリの定理（ファーリのていり、, ）はグラフ理論の定理で、任意の単純平面的グラフについて、その辺を交差しない線分によってできることを主張する。ハンガリーの数学者ファーリ・イシュトヴァーンの名を冠する。

、、 によって独立して証明された。定理にヴァーグナーの名を付すこともある。

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

証明

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

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

関連する結果 は、頂点の個数をとして格子上に線形対数時間で Fáry embedding を描画する方法を示した。この方法での面積のを与えることができる。 は類似の方法で必要な格子の面積を縮小し、半順序を基にしたの一つを証明した。シュナイダーの研究によって、極大な平面的グラフの辺をと呼ばれる3つの木に分割する特定の方法の存在が明示された。

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

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

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

は、任意の平面的グラフは、すべての辺が直線状であって辺長が整数である埋め込みを持つかという問題を提起した。と呼ばれるこの問題は未解決のままとなっている。立方体グラフにおいてはそのような埋め込みが存在することが知られている。

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

脚注

注釈

出典

参考文献 . . . . . . . . . . . . . 関連項目

四色定理