https://xuzijian629.hatenablog.com/entry/2019/08/24/173536

A separator theorem for minor-closed classes を読むと、minor-closedなグラフは $o(n)$ のseparatorを持つのでは？という話がされている。この論文では実際に、 $K_t$ をminorとして含まないようなグラフについて、 $O(t\sqrt{n})$ のseparatorを持つことを証明している。

したがって、bounded degreeのグラフは $O(d\sqrt{n})$ のseparator持つことがわかった。

考察として、 $K_t$ には辺が $O(t^2)$ 本含まれるため、辺の数が $O(n)$ のグラフだと、たかだか $O(\sqrt{n})$ な $t$ について $K_t$ しか含むことができない。

このままの条件だと、やはりほとんどすべてのbounded average degreeなグラフが $o(n)$ のseparatorを持つことができないことになってしまうが、 $o(\sqrt{n})$ な $t$ について $K_t$ しか含めないようなグラフは $o(\sqrt{n})$ のsepartorを持てることになる。

Strongly Sublinear Separators and Polynomial Expansion を読みたい。

平面グラフを拡張したクラス

平面グラフは平面(genus: 0)に埋め込めるグラフだが、これを拡張した概念として、torus(genus: 1)に埋め込めるトロイダルグラフや、それ以上のgenusについても考えることができる。

雑知見

一般グラフの最小交差数を求めることはNP-hardっぽい。与えられた $k$ についてグラフから $k$ 本の辺または頂点を削除して平面グラフにできるかの判定は線形時間っぽい

平面グラフの同型判定は線形時間らしい