普遍点集合

グラフ描画において、n次普遍点集合とは、ユークリッド平面上の点の集合Sであり、 n個の頂点を持つ平面グラフの頂点がすべてSの点に配置された直線描画が存在するという性質を持つ。

n ≤ 10の場合、ちょうどn個の点を持つ普遍的な点集合が存在するが、n  ≥  15 の場合は追加の点が必要となる。^{[ 1 ]}

いくつかの著者は、サイズO ( n ) × O ( n ) の整数格子の部分集合が普遍的であることを示しました。特に、de Fraysseix、Pach & Pollack (1988)は (2 n − 3) × ( n − 1) 点のグリッドが普遍的であることを示し、Schnyder (1990) はこれを ( n − 1) × ( n − 1) グリッドの三角形部分集合に縮小し、 n ² /2 − O ( n ) 点を持つようにしました。de Fraysseix らの方法を修正して、Brandenburg (2008) は任意の平面グラフを 4 n ² /9 点からなるグリッドの三角形部分集合に埋め込むことを発見しました。長方形グリッドの形の普遍点集合は少なくともn /3 × n /3 ^{[ 2 ]}のサイズを持つ必要がありますが、これは他のタイプのより小さな普遍点集合の可能性を排除するものではありません。既知の最小の普遍点集合はグリッドに基づくものではなく、代わりにスーパーパターン（与えられたサイズのすべての順列パターンを含む順列）から構築されます。このように構築された普遍点集合のサイズはn ² /4 − Θ ( n ) です。^{[ 3 ]}                    

de Fraysseix、Pach & Pollack (1988)は、 n + Ω(√ n )の形の境界で、普遍点集合のサイズに関する最初の非自明な下限を証明し、 Chrobak & Karloff (1989)は、普遍点集合には少なくとも 1.098 n − o ( n ) 個の点が含まれる必要があることを示しました。Kurowski (2004)は、1.235 n − o ( n )というさらに強い境界を述べており、 ^{[ 4 ]}これはScheucher、Schrezenmaier & Steiner (2018)によってさらに1.293 n − o ( n ) に改善されました。        

既知の線形下限と二次上限の間のギャップを埋めることは未解決の問題である。^{[ 5 ]}

平面グラフのサブクラスは、一般に、平面グラフのクラス全体よりも小さな普遍集合（サブクラス内のすべてのn頂点グラフを直線で描画できる点の集合）を持つ可能性があり、多くの場合、ちょうどn点の普遍点集合が可能です。たとえば、凸位置にあるn点の任意の集合（凸多角形の頂点を形成する）は、 n頂点の外平面グラフ、特に木に対して普遍的であることは容易にわかります。それほど明白ではありませんが、一般位置にあるn点の任意の集合（3 つの点が共線しない）は、外平面グラフに対して普遍的であり続けます。^{[ 6 ]}

入れ子サイクルに分割できる平面グラフ、2-外平面グラフ、および有界パス幅の平面グラフは、ほぼ線形サイズの普遍点集合を持つ。^{[ 7 ]}平面3木は、サイズO ( n ^3/2 log n )の普遍点集合を持つ。同じ境界は、直列並列グラフにも適用される。^{[ 8 ]}

直線グラフ描画だけでなく、他の描画スタイルについても普遍点集合が研究されてきました。これらの多くの場合、頂点が平面上の直線上に配置され、辺がこの直線を最大で1回だけ横切る曲線として描画される位相的ブック埋め込みに基づいて、ちょうどn個の点を持つ普遍点集合が存在します。たとえば、n個の共線点の任意の集合は、各辺が単一の半円または2つの半円から形成される滑らかな曲線として表現される円弧図に対して普遍的です。 ^{[ 9 ]}

同様のレイアウトを使用することで、平面上のすべての厳密に凸な曲線には、各辺につき最大 1 つの曲がりを持つポリライン描画に普遍的なn点サブセットが含まれていることが示されます。^{[ 10 ]}このセットには、曲がりではなく、描画の頂点のみが含まれています。すべての頂点とすべての曲がりがセット内に配置されたポリライン描画に使用できるより大きなセットが知られています。^{[ 11 ]}