Bidimensionality とは

二次元性理論は、広い範囲のグラフで効率的な近似、固定パラメータまたはカーネル解を認める幅広いグラフ問題(二次元)を特徴とする。これらのグラフクラスには、平面グラフ、マップグラフ、有界属グラフ、および固定小数点を除くグラフが含まれます。特に、二次元性理論は、数学的結果を拡張し、新しいアルゴリズム的ツールを構築することによって、RobertsonとSeymourのグラフのマイナーな理論に基づいています。この理論は、デメイン、フォミン、ハジャアヘイ、ティリコスの作品に導入され、2015年にネロデス賞を受賞しました。