n次元平面性グラフ

• 以前ZDDでのアルゴリズムの効率性を考えるときに「平面性グラフ」であることが登場した
• そのときに、より高次元の「平面性グラフ」の意味合いについてもちょっと考えた(こちら)
• n次元で「平面性なグラフ」：n次元でならば、交わることなく「きちんと描けるグラフ」があったときに、それをm (m < n)次元に落とすとエッジの交点が生じてしまう
• 次のような条件をつけることにする
  • m次元に落としたときに、m次元部分空間上にあったノードのみを残す
  • 残されたノードの間にm次元部分空間上にあったエッジがあれば、それは残す
  • 残されたノードの間に、残されなかったノードを解してパスがあれば、あらたにm次元部分空間上にエッジを作る。複数のパスがあった場合も１本のエッジに集約する
• このようにして作られたm次元空間のグラフが「m次元空間で平面性なグラフ」であるというとき、元のn次元グラフにはどんな制約があるだろう？？？？