文字列グラフ

グラフ理論では、ストリング グラフは平面上の曲線の交差グラフです。各曲線は「ストリング」と呼ばれます。グラフGが与えられた場合、各曲線の頂点と交差する曲線のペアごとに辺を持つグラフがGと同型になるような曲線またはストリングの集合が存在する場合にのみ、 Gはストリンググラフになります。

シーモア・ベンツァー (1959) は、遺伝子構造に適用されるストリンググラフに似た概念を説明しました。その文脈で、彼はまた、直線上で交差する区間、つまり今では古典的な区間グラフの族という特定のケースを提示しました。後に、シンデン (1966) は、同じアイデアを電気ネットワークとプリント回路に適用しました。ストリンググラフの数学的研究は、論文 Ehrlich、Even & Tarjan (1976) と、シンデンとロナルド・グラハムの共同研究から始まりました。そこで、ストリンググラフの特徴付けは、1976 年の第 5 回ハンガリー組合せ論コロキウムで未解決の問題として最終的に提起されました。^[1]しかし、ストリンググラフの認識は最終的にNP 完全であることが証明され、単純な特徴付けは存在しない可能性が高いことが示されました。^[2]

すべての平面グラフは文字列グラフです: ^[3]図に示すように、各頂点に対して、頂点の周りと各隣接する辺の中点の周りをループする文字列を描くことで、任意の平面埋め込みグラフの文字列グラフ表現を形成できます。グラフの任意の辺uvについて、 uとvの文字列はuvの中点付近で2回交差し、他の交差はないため、交差する文字列のペアは、元の平面グラフの隣接する頂点のペアを正確に表します。あるいは、円充填定理により、任意の平面グラフは円の集合として表すことができ、円の任意の2つは、対応する頂点が隣接している場合にのみ交差します。これらの円は（開始点と終了点が選択され、開いた曲線になります）、指定された平面グラフの文字列グラフ表現を提供します。 Chalopin、Gonçalves、Ochem (2007) は、上記の表現とは異なり、すべての平面グラフには各文字列のペアが最大で 1 つの交差点を持つ文字列表現があることを証明しました。 現在証明されているScheinerman の予想は、すべての平面グラフが文字列の非常に特殊なケースである直線セグメントの交差グラフによって表される可能性があるという、さらに強力な主張です。

与えられたグラフGのすべての辺が細分化されると、その結果得られるグラフはGが平面グラフである場合にのみ文字列グラフになります。特に、図に示されている完全グラフ K ₅の細分化は、 K ₅が平面グラフではないため、文字列グラフではありません。^[3]

すべての円グラフは、線分（円の弦）の交差グラフとして、文字列グラフでもあります。すべての弦グラフは文字列グラフとして表すことができます。弦グラフはツリーのサブツリーの交差グラフであり、対応するツリーの平面埋め込みを形成し、各サブツリーをサブツリーのエッジの周りをトレースする文字列に置き換えることによって、弦グラフの文字列表現を形成できます。

あらゆる比較グラフの補グラフも文字列グラフである。^[4]

Ehrlich、Even、Tarjan (1976) は、文字列グラフの彩色数の計算が NP 困難であることを示しました。Kratochvil (1991a) は、文字列グラフが誘導されたマイナー閉クラスを形成するが、グラフのマイナー閉クラスではないことを発見しました。

すべてのm辺の弦グラフは、 O ( m3 ^/ 4log1 ^/ 2m )個の頂点を除去することで、グラフ全体の定数分の2つの部分集合に分割できる。したがって、双クリークのない弦グラフ、つまり定数tに対してKt,t部分グラフ_を含ま_ない弦グラフは、O ( n )辺を持ち、より強く多項式展開を持つ。^[5]

• Benzer, S. (1959)、「遺伝的微細構造のトポロジーについて」、米国科学アカデミー紀要、45 (11): 1607–1620、Bibcode :1959PNAS...45.1607B、doi : 10.1073/pnas.45.11.1607、PMC  222769、PMID  16590553。
• Chalopin, J.; Gonçalves, D.; Ochem, P. (2007)、「平面グラフは 1-STRING である」、第 18 回 ACM-SIAM 離散アルゴリズムシンポジウムの議事録、ACM および SIAM、pp. 609–617。
• Dvořák, Zdeněk ; Norin, Sergey (2016)、「強準線形セパレータと多項式展開」、SIAM Journal on Discrete Mathematics、30 (2): 1095–1101、arXiv : 1504.04821、Bibcode :2015arXiv150404821D、doi :10.1137/15M1017569。
• エーリッヒ、G.; イーブン、S.;タージャン、RE (1976)、「平面における曲線の交差グラフ」、組合せ理論ジャーナル、21 (1): 8–20、doi : 10.1016/0095-8956(76)90022-8。
• Fox, Jacob ; Pach, János (2010)、「文字列グラフのセパレータ定理とその応用」、Combinatorics, Probability and Computing、19 (3​​): 371、doi :10.1017/s0963548309990459、S2CID  5705145。
• Golumbic, M.; Rotem, D.; Urrutia, J. (1983)、「比較可能性グラフと交差グラフ」、離散数学、43 (1): 37–46、doi : 10.1016/0012-365X(83)90019-5。
• グラハム、RL (1976)、「問題 1」、第 5 回ハンガリー組合せ論コロキウムにおける未解決問題。
• Kratochvil, Jan (1991a)、「ストリンググラフ。I. 臨界非ストリンググラフの数は無限である」、Journal of Combinatorial Theory、シリーズ B、52 (1): 53–66、doi : 10.1016/0095-8956(91)90090-7。
• Kratochvil, Jan (1991b)、「文字列グラフ。II. 文字列グラフの認識は NP 困難」、Journal of Combinatorial Theory、シリーズ B、52 (1): 67–78、doi : 10.1016/0095-8956(91)90091-W。
• Lovász, L. (1983)、「完全グラフ」、グラフ理論の選集、第 2 巻、ロンドン: アカデミック プレス、pp. 55–87。
• Pach, János ; Tóth, Geza (2002)、「文字列グラフの認識は決定可能」、Discrete & Computational Geometry、28 (4): 593–606、doi : 10.1007/s00454-002-2891-4。
• シェーファー、マーカス、ステファンコビッチ、ダニエル (2001)、「文字列グラフの決定可能性」、第 33 回 ACM コンピューティング理論シンポジウム (STOC 2001) の議事録: 241–246。
• シェーファー、マーカス; セジウィック、エリック; ステファンコビッチ、ダニエル (2003)、「NP における文字列グラフの認識」、コンピュータおよびシステム科学ジャーナル、67 (2): 365–380、doi : 10.1016/S0022-0000(03)00045-X。
• シンデン、FW (1966)、「薄膜RC回路のトポロジー」、ベルシステム技術ジャーナル、45 (9): 1639–1662、doi :10.1002/j.1538-7305.1966.tb01713.x。