A linear-time algorithm for drawing a planar graph on a grid
自分の問題の解決になるかなあと思って読んだけど特にならなかった。
https://xuzijian629.hatenadiary.jp/entry/2019/11/28/133732
こちらの記事とはかなりやり方が違う。
初めにtriangulateするところは同じだけど、かなり幾何的に埋め込んでいく。
平面グラフの埋め込みの問題の場合、triangulateしたものを埋め込んでもよく、triangulateされたグラフはcanonical orderingを持つので、良い性質を保ったままインクリメンタルに、構築できる、というのがよさそう。
平面グラフの描画とグリッドグラフの描画はやはりかなり訳が違いそう
