On Drawing Graphs With Right Angle Crossings

Radoslav Fulek, Balázs Keszegh, Filip Morić
http://arxiv.org/abs/1001.3117

以前紹介したWADS2009の論文の改善．
直角に辺交差するように描けるグラフ (ただし，辺は折れ線として描く) の辺の数がいくつになるか，という問題を考える．
この論文では各辺の折れ数が1のとき，辺の数がO(n)，折れ数が2のとき，辺の数がO(n log^2 n)であることを示している．
使っている技法はdischarging (「放電法」と訳されることもある) で，この手の問題でよく使われる方法ではあるけども，何に着目してdischargingを行うかが工夫のしどころになる．