平面グラフのトラック描画可能性判定問題の計算複雑度について

摘要

グラフは様々な関係を表現する離散構造であるが，グラフの描画には大きな任意性があるため，理解しやすいグラフの描画に関する研究が数多く存在する．例えば，より交差の少ない描画，各面の面積が均等な描画，2 つの枝のなす最小の角度が大きい描画等が理解しやすい描画として研究されている．