A string gráf egy síkban lévő görbék metszéspontjainak grafikonja , minden görbét "karakterláncnak" nevezünk. Adott egy G gráf akkor és csak akkor sztringgráf, ha a síkban olyan görbék (karakterláncok) vannak megrajzolva, amelyek nem metszik egymást ugyanabban a pontban, és a G gráf izomorf azzal a gráfmal, amelynek csúcsai megfelelnek a görbék és az ív ezen a grafikonon két görbe metszéspontjának felel meg.
Benzer ( 1959 ) a string gráfokhoz hasonló fogalmat írt le, de általánosabb struktúrákra. Ezzel összefüggésben megfogalmazta az intervallumok egy egyenes metszéspontjának speciális esetét is, amely az intervallumgráfok klasszikus osztályává vált . Sinden ( 1966 ) később ugyanezt az elképzelést fogalmazta meg az elektromos hálózatokra és a nyomtatott áramkörökre vonatkozóan. A húrgráfok matematikai tanulmányozása Ehrlich , Even, Tarjan (1976 ) tanulmányával kezdődött, majd Sinden és Ronald Graham közreműködésével a húrgráfok leírását végül az V. Kombinatorika Magyar Kollokviumon nyitott problémaként tették fel. 1976 [1] . Végül is bebizonyosodott, hogy a sztringgráf-felismerés egy NP-teljes probléma , ami azt jelenti, hogy ennek az osztálynak alig van egyszerű leírása [2]
Bármely síkgráf egy karakterlánc [3] - bármilyen síkba ágyazott gráfhoz létrehozhat egy sztringgráf-ábrázolást úgy, hogy minden egyes csúcshoz görbét rajzol, amely az egyes szomszédos élek csúcsa és felezőpontja körül megy, az ábrán látható módon. A gráf bármely uv élére az u és a v karakterláncai kétszer metszik egymást az uv él közepe közelében , és nincs más metszéspont, így egy karakterláncpár metszéspontja az eredeti síkgráf szomszédos csúcspárjait jelenti. Alternatív megoldásként a körcsomagolás tételével bármely síkgráf ábrázolható körök halmazaként, amelyek közül bármelyik kettő akkor és csak akkor metszi egymást, ha a megfelelő csúcsok szomszédosak. Ezek a körök (a kezdő- és végpontokkal úgy, hogy a kör nyílt görbévé váljon) adják az adott síkgráf karakterlánc-ábrázolását. Chalopin, Gonçalves és Ochem ( Chalopin, Gonçalves, Ochem 2007 ) bebizonyította, hogy minden síkgráfnak van egy sztringgráf-reprezentációja, amelyben minden húrpárnak legfeljebb egy metszéspontja van, nem a fent leírtak szerint. A most bevált Scheinerman-sejtés egy még szigorúbb állítás, amely szerint bármely síkgráf ábrázolható vonalszakasz-metszésgráfként. x Ha egy adott G gráf minden éle fel van osztva , akkor az eredményül kapott gráf akkor és csak akkor lesz string gráf, ha G sík. Konkrétan a teljes gráf K 5 ábrán látható felosztása nem sztringgráf, mivel K 5 nem síkbeli [3] .
Bármely körkörös gráf , mint például a vonalszakaszok metszéspontjainak grafikonja (a kör húrjai) is sztringgráf. Bármely akkordgráf ábrázolható sztringgráfként – az akkordgráfok fák részfáinak metszésponti gráfjai, és egy akkordgráf karakterlánc-ábrázolása hozható létre úgy, hogy a megfelelő fát síkban beágyazzuk, és minden részfát egy sztringgel helyettesítünk, amely körbefutja a fák éleit. a részfa.
Bármely összehasonlíthatósági gráf gráf komplementere is egy string gráf [4] .
Ehrlich, Even és Tarjan ( Ehrlich, Even, Tarjan 1976 ) kimutatta, hogy a sztringgráf kromatikus számának kiszámítása NP-nehéz probléma. Kratochvil ( 1991a ) azt találta, hogy a string gráfok a generált minorok zárt osztályát alkotják, de nem egy kisebb zárt gráfosztályt.
Bármely m élű stringgráf két részhalmazra bontható, amelyek mindegyike a teljes gráf fix része, O ( m 3/4 log 1/2 m ) él eltávolításával. Ebből következik, hogy a kattintásmentes stringgráfok, a K t , t részgráfokat nem tartalmazó sztringgráfok bármely t konstanshoz O ( n ) élekkel és polinomiális kiterjesztéssel [5] [6] .