平面直線グラフ（PSLG）とは？定義からデータ構造まで徹底解説

平面直線グラフ（PSLG）の定義

計算幾何学において、平面直線グラフ（PSLG：Planar Straight-Line Graph）とは、平面グラフを平面上に埋め込み、そのすべての辺を直線分として表現したグラフ構造を指します。「ストレートライン平面グラフ」「平面ストレートライングラフ」などと呼ばれることもあります。

ファーリーの定理（Fáry's theorem、1948年）によれば、あらゆる平面グラフは必ずこの種の埋め込みを持つことが証明されており、これがPSLGの理論的な基盤となっています。

平面分割としてのPSLG

計算幾何学の文脈では、PSLGはしばしば「平面分割（planar subdivision）」とも呼ばれます。この場合、分割された領域は多角形であることが前提となります。

また、次数1の頂点が存在しない場合、PSLGは「平面を多角形領域へ分割したもの」と等価に扱えます。次数1の頂点を排除することで、各種アルゴリズムの記述が大幅に簡素化されますが、これは必須の条件ではなく、あくまで便宜上の取り決めです。

主な応用例

PSLGは多様な地図情報の表現に活用されています。代表的な応用例として、地理情報システム（GIS）における地理マップの表現が挙げられます。道路網や行政区域などの空間データを効率的に管理する基盤技術となっています。

特殊ケース：三角化（トライアンギュレーション）

PSLGにはいくつかの重要な特殊ケースがあり、中でも三角化（triangulation）が代表例です。具体例には以下が含まれます。

• 多角形の三角分割（polygon triangulation）
• 点集合の三角分割（point set triangulation）

特に点集合の三角分割は「最大PSLG」と呼ばれる特徴を持ちます。これは、グラフの平面性を維持したまま新たな直線辺を追加できない状態、すなわちこれ以上辺を増やせない極大の構造を意味します。三角分割はコンピュータグラフィックス、メッシュ生成、地理解析など、非常に幅広い分野で応用されています。

ユークリッドグラフとの関係

PSLGはユークリッドグラフの一種と見なすことも可能です。ただし、両者では関心の対象となる性質が異なります。

• ユークリッドグラフ： 頂点間の距離といった距離的（メトリック）性質が主な関心事
• PSLG： 辺の接続関係など位相的（トポロジー的）性質が主な関心事

なお、ドロネー三角分割のように、距離的性質と位相的性質の両方が重要となるグラフも存在します。

PSLGを表現する3つのデータ構造

PSLGは、以下の3つの著名なデータ構造によって表現されます。それぞれに特徴と得意分野があります。

1. ウィングドエッジ構造（Winged-edge data structure）

3つの中で最も古くから知られている古典的なデータ構造です。しかし、辺の参照が辺の方向を保持しておらず、さらに同一の面を囲む辺たちの向きが一貫していないため、実際の操作には複雑な場合分けが必要になりがちです。

2. ハーフエッジ構造（Halfedge data structure）

各辺について両方向の情報を個別に格納し、それらを適切に相互リンクさせる構造です。これにより操作ロジックと格納方式がシンプルになり、実装のしやすさから広く利用されています。

3. クアッドエッジ構造（Quadedge data structure）

平面分割とその双対グラフを同時に格納できる点が最大の特徴です。レコードは辺の記録のみで構成され、各辺につき4つのレコードを持ちます。簡略化された形式では、PSLGの格納にも活用できます。

まとめ

平面直線グラフ（PSLG）は、計算幾何学における基礎的なデータ構造であり、GISやメッシュ生成など実用的な分野で広く活用されています。目的に応じてウィングドエッジ、ハーフエッジ、クアッドエッジの3つの表現方法を使い分けることで、効率的な処理が可能となります。