Embedding Planar Graphs on the Grid

www.semanticscholar.org

無料PDFが見つからなかったのでスライドを読んだ。

https://pdfs.semanticscholar.org/9c89/7e65499cc6caacabd8abab6071010b03248c.pdf?_ga=2.178289380.1937718360.1574912307-1595927464.1574667430

アルゴリズムは3ステップに別れる。

1. 直線の描画を与える

. 実数座標になっていることに注意

2. 三角形分割する

3. Normal Labelingをする

これは、各頂点の適当な3点についての重心座標を求め、最も上のものを1, 次に最も右のものを2, 残りを3のようにするラベリング

4. 各点から、重心座標のもとになった3点に向かう3本のパスを求める

これによって領域が3つに分割される。それぞれの領域に三角形がいくつあるかをカウントする

5. 座標を計算