数学やコンピュータサイエンスにおいて、「平面グラフ」と「平面的グラフ」という用語が使用される場面がありますが、これらは微妙に異なる意味を持っています。この記事では、それぞれの定義や特徴、違いについて詳しく解説します。
平面グラフとは？
平面グラフ（Plane Graph）は、以下のように定義されます。
平面グラフとは、グラフを平面上に描いたときに、どの2つの辺も交わらないように配置できるグラフのことです。
特徴：
- 辺の交差がないように描画可能。
- グラフが平面上に「埋め込まれている」状態を指す。
- ノード（頂点）やエッジ（辺）の位置が具体的に決められた図形。
例えば、以下のグラフは平面グラフに該当します：
- 三角形（3頂点の完全グラフ）
- 四角形など単純なポリゴンのグラフ
平面的グラフとは？
平面的グラフ（Planar Graph）は、平面グラフと似ていますが、より一般的な概念です。
平面的グラフとは、グラフが平面上に描画可能かどうかを表す性質を指します。すなわち、「平面グラフに変換可能なグラフ」のことです。
特徴：
- 実際の描画の仕方は問わず、その描画可能性が重要。
- 初期のグラフが複雑でも、再配置することで平面グラフにできる場合があります。
- グラフの「性質」として考えられる。
例：
- 5つの頂点を持つグラフ（K₅）は平面的ではありません。
- ただし、K₄（4頂点の完全グラフ）は平面的です。
※「K」はグラフの種類を表す記号で、頂点数を示す「n」とともに完全グラフや完全二部グラフを特定します。
平面グラフと平面的グラフの違い
以下に主な違いを整理します：
| 項目 | 平面グラフ | 平面的グラフ |
| 定義 | 平面上で描画された状態のグラフ | 平面上で交差せずに描画可能なグラフ |
| 具体性 | 実際の描画にフォーカス | 描画可能性という性質にフォーカス |
| 応用例 | 図形やネットワークの具体的な可視化 | グラフ理論やアルゴリズムの研究 |
平面的グラフを判定するアルゴリズム
平面的グラフであるかを調べるためには、いくつかの有名な方法や理論があります。
- クルトフスキーの定理
グラフが平面的であるためには、以下の2つのグラフ（K₅とK₃,₃）を部分グラフとして持たない必要があります。
- K₅：5頂点の完全グラフ
- K₃,₃：二部グラフ（3対3の完全二部グラフ）
- DFSベースのアルゴリズム
深さ優先探索を利用して平面的かどうかを調べる方法もあります。
これらの技術は、グラフ描画やネットワーク設計において実用的です。
実用例と応用分野
平面グラフと平面的グラフの概念は、多くの分野で応用されています。
- 地図の分割問題
地図上で国や州を描画するとき、隣接する領域が正確に表されるようにする必要があります。この場合、地図自体は平面的グラフで表現されます。
- VLSI設計
電子回路設計において、回路の配線が交差しないようにするために平面グラフの概念が活用されます。
- データビジュアライゼーション
ノードリンク図などのグラフ描画において、平面的グラフのアルゴリズムが利用されます。
まとめ
平面グラフと平面的グラフの違いは、実際の描画か、その性質に重点を置くかという点にあります。平面グラフは具体的な図形としての状態を指し、平面的グラフはその描画可能性という特性を表します。これらの概念を正しく理解することで、グラフ理論や応用分野での課題解決がより効率的になります。
