PQ木を用いたグラフの平面性判定

## はじめに

平面性判定アルゴリズムとは、あるグラフが平面的グラフかどうかを判定する問題です。
アルゴリズムはいくつも存在し、それらについては[英語版WikipediaのPlanarity_testing](https://en.wikipedia.org/wiki/Planarity_testing)に書いてありますので、こちらを参考にしてください。

ここで扱う平面性判定アルゴリズムは、PQ木を用いた点付加アルゴリズム（Vertex addition method）[^1]です。
以降で使用する画像については同論文からの引用となります。

最初にPQ木について説明し、そのあとでアルゴリズム全体を説明します。

## PQ木

ざっくりいうと、特定の要素の順序を保持したまま、任意の順列を表現する木構造になります。

子要素の順序が任意のPノードと、子要素の順序が固定のQノード、それと実際の値が格納された葉ノードの三種類のノードを使います。

図ではPノードは丸、Qノードは四角で記されます。
![P-node](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/764695/ddb42481-58a8-ece9-66c2-23f2196103f2.png) ![Q-node](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/764695/dd165d54-2202-769f-0934-e838916a7374.png)

例えば、AからKまでのアルファベットを値とするPQ木の一例として、次のようなものがあります。

![PQ-tree.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/764695/1c2e3fa9-11fc-ae81-794d-48f0600af7c8.png)

## 型紙合せ（Pattern matching）

型紙合せという手順でPQ木を変形することができます。

型紙合せは、木の中に存在する任意個の値を指定して、木の葉要素から根に向かって順番に実行する操作です。

このとき、ノードの状態を次のように定義しておきます。

- Full：自分（か、その全ての子孫要素）に格納された値全てが、指定された値に含まれている状態
- Empty：自分（か、その全ての子孫要素）に格納された値全てが、指定された値に含まれていない状態
- Partial：FullでもEmptyでもない状態

木自体を変形するとともに、このノードの状態を伝播させていきます。
図では、斜線の入った要素がFull、斜線の入っていない要素がEmptyを意味します。

また、子孫要素以外には指定された値が含まれていないノードをROOTとし、このノードに到達した時点で処理を終了します。

Pノード、Qノード共通で２パターン、Pノードには５パターン、Qノードには２パターンのテンプレートがあります。

### 初期化

初期化は簡単で、全ての葉ノードについて、そこに格納された値が指定された値に含まれているかどうかをFullかEmptyでマークしていきます。

### 共通

共通パターンは次の二つです。

![P0P1](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/764695/a4b1494b-51a3-f2a2-f646-7b7b0f2ba24c.png)

左は子要素全てがEmptyの場合で、この時は自分もEmptyとマークします。
右は子要素全てがFullの場合で、この時は自分もFullとマークします。

### Pノード

Pノードは順不同のため、子要素を任意に入れ替えて指定したパターンに当てはまった場合はそれを適用します。

#### P2

操作対象のノードがROOTであり、Partialなノードが子要素に存在しないとき、次のように変形します。

![P2](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/764695/bed1f4dc-dce5-b439-fb0e-f76033a8d33d.png)

#### P3

操作対象のノードがROOTではなく、Partialなノードが子要素に存在しないとき、次のように変形します。

![P3](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/764695/312e2560-dee6-3f6e-a985-48d009c0b0e4.png)

なお、EmptyやFullの要素が一つの場合は、次のように変形してもよいです。

![P3-alt](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/764695/2bfc66c5-a5d0-ca34-df78-c2605f2b196f.png)

#### P4

操作対象のノードがROOTであり、Partialなノードが子要素に１つだけ存在するとき、次のように変形します。

![P4](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/764695/c83db7f4-013f-d830-88df-2b422a8ce3ef.png)

#### P5

操作対象のノードがROOTではなく、Partialなノードが子要素に１つだけ存在するとき、次のように変形します。

![P5](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/764695/29f36204-22a4-2419-3604-71fd677ab5d6.png)

#### P6

操作対象のノードがROOTであり、Partialなノードが子要素に２つ存在するとき、次のように変形します。

![P6](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/764695/180343ab-d629-169f-a8f0-a36e9bda63ba.png)

### Qノード

Qノードは順序固定のため、子要素の順序を入れ替えずに指定したパターンに当てはまった場合はそれを適用します。

また、以下のQ2およびQ3は一部のパターンでしかありません。やりたいことはいずれにしても、Fullなノードを一か所に集めることです。
なので、図中のPartialなノードがなかったり、連続したEmptyまたはFullのノードが無かったりしても、同様に適用します。

#### Q2

操作対象のノードにPartialなノードが子要素に１つ以下存在するとき、次のように変形します。

![Q2](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/764695/b078d9e5-b688-889c-1dbe-dc846bcd4a62.png)

#### Q3

操作対象のノードがROOTであり、Partialなノードが子要素に２つ以下存在するとき、次のように変形します。

![Q3](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/764695/a6cd2d00-db54-83a9-301a-f1e2d61386fd.png)

### マッチしなかった場合

上記のいずれのパターンにも合致しなかった場合は、不適格となります。

## 平面性判定

PQ木を用いた平面性判定アルゴリズムの全体像とst-番号付けはこの論文[^2]が、PQ木の操作についてはPQ木が紹介されている論文[^1]が、それぞれ詳しいです。
なお、Bubble処理を行うことによる効率的なアルゴリズムが説明されていますが、ここではその処理は行いません。（私がまだその処理を理解しきれていないためです）

以下、アルゴリズムです。なお、処理対象とするグラフを$G$、その各ノードを$N_i$などと記載しています。

1. グラフ$G$が非連結の場合は、それぞれの連結成分で次の処理を行う
1. グラフ$G$に関節点が存在する場合は、その~~関節点を取り除いたときの非連結要素に関節点自身と枝を追加したグラフ~~二重連結成分（Biconnected component）それぞれで次の処理を行う
1. $G$にst-番号付けを行う
1. Pノードを根、st-番号の一番小さなグラフ$G$の要素$N_1$に隣接する要素$N_i$を値に持つノードを葉としたPQ木$T$を作る
1. $G$のst-番号の二番目に小さな要素$N_2$から順に、次の処理を行う
    1. 対象の要素$N_i$を指定して$T$の型紙合せを行う
    1. 不適格だった場合は$G$は非平面的グラフと決定される
    1. $T$の中の（FullあるいはPartialとなった）ROOTについて
        - Pノードの場合、その子要素を$G$の要素$N_i$の隣接要素のうち、まだ処理を行っていないものに置き換える
        - Qノードの場合、その連続したFullの要素をPノードに置き換え、その子要素に$G$の要素$N_i$の隣接要素のうち、まだ処理を行っていないものを置く
          また、これによってQノードの要素が2個になった場合は、Pノードに変更する
1. $G$が非平面グラフと決定されなかった場合、$G$は平面グラフである

## 実装

JavaScriptによる実装を行いました。
かなり汚いですが、参考になれば幸いです。

https://github.com/ai-on-browser/ai-on-browser.github.io/blob/4ee43f9fa180d5506c67c25e1be24a1ac16105a0/lib/util/graph.js#L1864

[^1]: Kellogg S. Booth, George S. Lueker, "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms", Journal of computer and system sciences, 13, pp. 335-379 (1976)
[^2]: 西関 隆夫, "32. グラフの平面性判定法", 情報処理, Vol. 24, No. 4, pp. 521-528 (1983)