「平面」とはどういう意味ですか？
目次
平面グラフって、紙みたいなフラットな表面に描けて、エッジが交差しないグラフのことだよ。簡単に言うと、線が重ならないように描けるグラフは平面グラフって呼ばれる。
平面描画のタイプ
平面描画にはいろんな種類があって、エッジが交差するのを許すものや、そうじゃないものがあるんだ。場合によっては、エッジが交差する回数が限られてるのもあるよ。これがk-平面グラフっていうアイデアにつながってて、各エッジが交差できる回数を「k」としてる。
クラスタ平面性
クラスタ平面性っていうのは特別なケースで、いくつかの頂点が形や境界で囲まれてるグループ、つまりクラスタがある状態のこと。これによってグラフがより整理されるんだ。クラスタ平面性の古典的なバージョンでは、形は凸でないといけなくて、くぼみがないってこと。
最近のクラスタ平面性のバージョンでは、これらのクラスタの形がもっと柔軟に許可されてる。たとえば、あるバージョンでは、エッジを頻繁に交差させない限り、曲線で囲まれたクラスタが許可されてる。
平面グラフの課題
平面描画の中には簡単に作れるものもあれば、かなり難しいものもある。たとえば、特定の条件で解決できるクラスタ平面のセットアップもあれば、対処がすごく難しいものもあるんだ。複雑さが増すと、交差なしでグラフを表現する方法を見つけるのが難しくなるよ。
シンプルな描画と一般的な描画
平面グラフの世界には、シンプルな描画と一般的な描画の概念もある。シンプルな描画はルールが厳しくて、エッジは1回しか交差できないし、同じ頂点を共有するエッジは交差してはいけない。一方、一般的な描画は交差にもっと柔軟性がある。
面白いことに、リラックスした感じに描けるグラフもあるけど、シンプルなルールに交差を制限しようとすると問題が起きることがある。これが、同じ基盤の構造であっても、グラフ描画がどれだけ複雑になりうるかを示してるんだ。