Řetězcový graf je graf průsečíků křivek v rovině, přičemž každá křivka se nazývá „řetězec“. Je- li dán graf G , jedná se o řetězcový graf tehdy a jen tehdy, pokud existuje množina křivek (řetězců) nakreslených v rovině tak, že se žádné tři řetězce neprotínají ve stejném bodě a graf G je izomorfní s grafem, jehož vrcholy odpovídají křivky a oblouk v tomto grafu odpovídají průsečíku dvou křivek.
Benzer ( 1959 ) popsal koncept podobný řetězcovým grafům, ale pro obecnější struktury. V této souvislosti také formuloval speciální případ průniku intervalů na přímce, který se stal klasickou třídou intervalových grafů . Sinden ( 1966 ) později vyjádřil stejnou myšlenku pro elektrické sítě a tištěné obvody. Matematické studium řetězcových grafů začalo prací Ehrlicha , Evena, Tarjana (1976 ) a s pomocí Sindena a Ronalda Grahama byl popis řetězcových grafů nakonec nastolen jako otevřený problém na 5. maďarském kolokviu o kombinatorice v 1976 [1] . Koneckonců bylo prokázáno, že rozpoznávání řetězcových grafů je NP-úplný problém , což znamená, že neexistuje jednoduchý popis této třídy [2]
Libovolný rovinný graf je řetězec [3] – můžete vytvořit řetězcovou grafovou reprezentaci pro jakýkoli graf vložený do roviny nakreslením křivky pro každý vrchol, která prochází kolem vrcholu a středu každé sousední hrany, jak je znázorněno na obrázku. Pro libovolnou hranu uv grafu se řetězce pro u a v protínají dvakrát poblíž středu hrany uv a neexistují žádné další průsečíky, takže průsečík dvojice řetězců představuje sousední dvojice vrcholů v původním rovinném grafu. Alternativně, pomocí teorému o sbalení kružnic , může být jakýkoli rovinný graf reprezentován jako sbírka kružnic, z nichž jakékoli dva se protínají právě tehdy, když jsou odpovídající vrcholy sousedící. Tyto kružnice (s počátečním a koncovým bodem vybraným tak, aby se kružnice stala otevřenou křivkou) dávají řetězcové grafové znázornění daného rovinného grafu. Chalopin, Gonçalves a Ochem ( Chalopin, Gonçalves, Ochem 2007 ) dokázali, že jakýkoli rovinný graf má reprezentaci řetězcového grafu, ve kterém má každá dvojice řetězců nejvýše jeden průsečík, ne jak je popsáno výše. Scheinermanova domněnka , nyní dokázaná, je ještě přísnější tvrzení, že jakýkoli rovinný graf může být reprezentován jako graf průsečíku úsečky. x Pokud jsou všechny hrany daného grafu G rozděleny , výsledný graf je řetězcový graf právě tehdy, když G je rovinný. Zejména poddělení úplného grafu K 5 znázorněného na obrázku není řetězcový graf, protože K 5 není rovinný [3] .
Jakýkoli kruhový graf , jako je graf průsečíků úseček (tetivy kruhu), je také řetězcový graf. Jakýkoli akordický graf může být reprezentován jako řetězcový graf - akordické grafy jsou průsečíkové grafy podstromů stromů a lze vytvořit řetězcovou reprezentaci akordického grafu plošným vložením odpovídajícího stromu a nahrazením každého podstromu řetězcem procházejícím kolem okrajů stromu. podstrom.
Grafovým doplňkem každého grafu srovnatelnosti je také řetězcový graf [4] .
Ehrlich, Even a Tarjan ( Ehrlich, Even, Tarjan 1976 ) ukázali, že výpočet chromatického čísla řetězcového grafu je NP-obtížný problém. Kratochvil ( 1991a ) zjistil, že řetězcové grafy tvoří uzavřenou třídu generovaných nezletilých, ale ne menší uzavřenou třídu grafů.
Jakýkoli řetězcový graf s m hranami lze rozložit na dvě podmnožiny, přičemž každá podmnožina je pevným zlomkem úplného grafu, odstraněním O ( m 3/4 log 1/2 m ) hran. Z toho vyplývá, že řetězcové grafy bez kliky , řetězcové grafy neobsahující žádné podgrafy K t , t pro žádnou konstantu t , mají O ( n ) hran a mají polynomiální rozšíření [5] [6] .