グラフ埋め込み

位相グラフ理論では、グラフの面への埋め込み（ imbeddingとも綴る）は、 の点が頂点に関連付けられ、単純な弧（の同相像）が次のように 辺に関連付けられた、 上のの表現です。 ${\displaystyle G}$ ${\displaystyle \Sigma }$${\displaystyle G}$${\displaystyle \Sigma }$${\displaystyle \Sigma }$${\displaystyle [0,1]}$

• エッジに関連付けられた円弧の端点は、${\displaystyle e}$${\displaystyle e,}$
• 弧には他の頂点に関連付けられた点が含まれない。
• 2 つの円弧は、どちらかの円弧の内側の点で交差することはありません。

ここで、表面は連結された 多様体です。 ${\displaystyle 2}$

非公式には、グラフを面上に埋め込むとは、グラフの辺が端点でのみ交差するように面上にグラフを描くことである。任意の有限グラフを3次元ユークリッド空間に埋め込むことができることはよく知られている。^[1]平面グラフは2次元ユークリッド空間に埋め込むことができるグラフである。${\displaystyle \mathbb {R} ^{3}}$${\displaystyle \mathbb {R} ^{2}.}$

多くの場合、埋め込みは、先ほど説明した種類の表現の 同値類（ の同相写像の下で）と見なされます。${\displaystyle \Sigma }$

一部の著者は、エッジの非交差条件を省略することで、「グラフ埋め込み」の定義の弱いバージョンを定義しています。このような文脈では、より厳密な定義は「非交差グラフ埋め込み」として説明されます。^[2]

この記事では、グラフ埋め込みの厳密な定義のみを扱います。より弱い定義については、「グラフ描画」および「交差数」の記事で説明します。

グラフが閉じた曲面 に埋め込まれている場合、 の頂点と辺に関連付けられた点と弧の和の補集合は、領域（または面）の族です。 ^[3] 2セル埋め込み、セルラー埋め込み、またはマップは、すべての面が開円板に同相である埋め込みです。^[4]閉じた2セル埋め込みは 、すべての面の閉包が閉円板に同相である埋め込みです。 ${\displaystyle G}$${\displaystyle \Sigma }$${\displaystyle G}$

グラフの種数は、グラフを種数の表面に埋め込むことができる最小の整数です。特に、平面グラフは、自己交差することなく球面上に描画できるため、種数は です。トーラスに埋め込むことができるグラフは、トーラスグラフと呼ばれます。 ${\displaystyle n}$ ${\displaystyle n}$${\displaystyle 0}$

グラフの非向き付け種数は、グラフが（非向き付け）種数の非向き付け表面に埋め込むことができる最小の整数である。^[3]${\displaystyle n}$${\displaystyle n}$

グラフのオイラー種数は、グラフが (有向可能な) 種数の有向面または (非有向可能な) 種数の非有向面に埋め込むことができる最小の整数です。オイラー種数が非有向可能な種数よりも小さい場合、 グラフは有向的に単純です。${\displaystyle n}$${\displaystyle n/2}$${\displaystyle n}$

グラフの最大種数は、種数の向き付け可能な曲面にグラフが - セルに埋め込まれることができる最大の整数です。 ${\displaystyle n}$${\displaystyle 2}$ ${\displaystyle n}$

埋め込みグラフは、同じ頂点に接する辺の巡回順序を一意に定義する。これらの巡回順序の集合は回転システムと呼ばれる。同じ回転システムを持つ埋め込みは同等であると見なされ、対応する埋め込みの同値クラスは組み合わせ埋め込みと呼ばれる（点と曲線に関する前述の定義を指す位相埋め込みという用語とは対照的である）。回転システム自体が「組み合わせ埋め込み」と呼ばれることもある。^{[5] [6] [7]}

埋め込みグラフは、埋め込みの面の境界を構成するエッジの自然な循環順序も定義します。ただし、これらの面ベースの順序の処理はそれほど簡単ではありません。一部のエッジが面の境界に沿って 2 回トラバースされる場合があるためです。たとえば、これは 1 つの面を持つツリーの埋め込みでは常に当てはまります。この組み合わせの厄介さを克服するには、すべてのエッジを縦方向に 2 つの「ハーフエッジ」または「サイド」に「分割」することを検討できます。この規則では、すべての面境界トラバースで各ハーフエッジは 1 回だけトラバースされ、同じエッジの 2 つのハーフエッジは常に反対方向にトラバースされます。

セル埋め込みの他の同等の表現には、埋め込みグラフの頂点と辺の位相ディスクを接着して形成される位相空間であるリボン グラフと、埋め込みグラフの各辺に 4 つの頂点を持つ辺色付き立方体グラフであるグラフエンコード マップ があります。

グラフの種数を見つける問題はNP困難である（ -頂点グラフに種数があるかどうかを判断する問題はNP完全である）。^[8]${\displaystyle n}$${\displaystyle g}$

同時に、グラフの種数問題は固定パラメータで扱いやすく、つまり、グラフが与えられた固定種数の表面に埋め込まれるかどうかをチェックしたり、埋め込みを見つけたりするための多項式時間アルゴリズムが知られています。

この点における最初のブレークスルーは1979年に起こりました。時間計算量 O ( nO ^{( g ) )のアルゴリズムが}、ACMの年次計算理論シンポジウムに独立して提出されたのです。1つはI. FilottiとGL Millerによるもので、もう1つはJohn Reifによるものでした。彼らのアプローチは全く異なっていましたが、プログラム委員会の提案により共同論文を発表しました。^[9]しかし、Wendy MyrvoldとWilliam Kocayは2011年にFilotti、Miller、Reifが示したアルゴリズムが間違っていることを証明しました。^[10]

1999年に、種数が固定の場合、グラフサイズに対して線形、種数に対して二重指数関数的に時間的に解くことができることが報告されました。 ^[11]

任意の有限グラフは3次元空間に埋め込むことができることが知られています。^[1]

これを行う 1 つの方法は、点を空間内の任意の線上に配置し、各エッジを曲線として描画することです。各曲線は、異なる半平面上にあり、すべての半平面はその線を共通の境界とします。このようにエッジが半平面上に描画される埋め込みは、グラフのブック埋め込みと呼ばれます。この比喩は、エッジが描画される各平面が本のページのようなものだと想像することから来ています。実際には、同じ「ページ」に複数のエッジが描画される可能性があることが観察されました。グラフの本の厚さは、そのような描画に必要な半平面の最小数です。

あるいは、どの有限グラフも、その頂点を一般的な位置に配置して、どの 4 つの頂点も同一平面上にないようにすることで、交差のない 3 次元の直線の辺で描くことができます。たとえば、これは、i番目の頂点をモーメント曲線の点​​ ( i , i ² , i ³ )に配置することで実現できます。

2 つのサイクルが位相的にリンクされていない 3 次元空間へのグラフの埋め込みは、リンクレス埋め込みと呼ばれます。グラフがリンクレス埋め込みを持つのは、ピーターセン族の 7 つのグラフの 1 つをマイナーとして持たない場合のみです。

• 
  射影平面に埋め込まれたピーターセン グラフと関連マップ。円上の反対の点が識別され、向き付け不可能な種数 1 の閉じた表面が生成されます。
• 
  トーラスに埋め込まれたパップス グラフと関連マップ。
• 
  種数 3 の有向曲面に埋め込まれた次数 7 のクライン グラフと関連マップ。

• 埋め込み（他の種類の埋め込みの場合）
• 本の厚さ
• グラフの太さ
• 二重連結エッジリスト、平面に埋め込まれたグラフを表すデータ構造
• 正則写像（グラフ理論）
• ファリーの定理は、平面グラフの直線平面埋め込みは常に可能であることを述べています。
• 三角測量（幾何学）