Optimal stochastic planarization

論文紹介

Anastasios Sidiropoulos
http://arxiv.org/abs/1004.1666

種数gのグラフを平面的グラフ (種数0のグラフ) に埋め込むときに歪みをできるだけ小さくしたいという話があり，最適な歪みO(log g)を達成する埋め込みを多項式時間で見つけることができるようになりました，という話．