n次元平面性グラフ？

• こちらで平面性グラフでのフロンティア構成ノード数の上限の話とか、それがSimPath/ZDDアルゴリズムとどういう関係にあるかについて触れた
• 一般化するのは悪くないので、フロンティアの一般化…
• 平面性グラフは２次元空間にエッジの交叉を作らないで埋め込むことができるグラフ
• では、3,4,...と次元を上げると、「結び目・絡み目」的な話にするのか…
• 「平面的」に広がりながらもユークリッド平面に納まりきらない双曲幾何的(こちらとか)な方向・その逆で球面に小さく納める、とかいう「曲がった平面」の一般次元化したときのこととするのか…
• 別の考え方で、フロンティアはグラフノードを３群に分けて、そのうちの２群の間を結ぶエッジがないようにすることであるときに、「フロンティア集合」の個数の最大値を平面性に関わらず、知る方法として、何か良い方法がないのかという話にするのか…
• 次元を上げるときには、「２次元空間でエッジ(線分)が交差する」を「n次元空間でn-1次元ハイパーエッジが交差する」と読み替えるのはありだろう
• フロンティア集合の個数の最大値の問題は「グラフカット」とか「連結性」とかの話題なので、そこでの知見から掘り出せばよさそう
  • 「最小」は話題になりがちだけれど(最大フロー最小カット問題)、「最大」は話題として小さい印象がある