Un grafic cu șiruri este un grafic al intersecțiilor curbelor dintr-un plan, fiecare curbă fiind numită „șir”. Având în vedere un grafic G , acesta este un grafic cu șiruri dacă și numai dacă există o mulțime de curbe (șiruri) desenate în plan astfel încât să nu se intersecteze trei șiruri în același punct și graficul G este izomorf cu graficul ale cărui vârfuri corespund cu curbele și arcul din acest grafic corespunde intersecției a două curbe.
Benzer ( 1959 ) a descris un concept similar graficelor cu șiruri, dar pentru structuri mai generale. În acest context, el a formulat și un caz special de intersecție a intervalelor pe o dreaptă, care a devenit clasa clasică de grafice de intervale . Sinden ( 1966 ) a exprimat mai târziu aceeași idee pentru rețelele electrice și circuitele imprimate. Studiul matematic al graficelor cu șiruri a început cu o lucrare a lui Ehrlich , Even, Tarjan (1976 ) și, cu asistența lui Sinden și Ronald Graham, descrierea graficelor cu șiruri a fost în cele din urmă pusă ca o problemă deschisă la cel de-al 5-lea Colocviu maghiar de combinatorie din 1976 [1] . La urma urmei, s-a dovedit că recunoașterea graficului de șiruri este o problemă NP-completă , ceea ce implică că nu există o descriere simplă a acestei clase [2]
Orice grafic planar este un șir [3] - puteți forma o reprezentare grafică șir pentru orice grafic încorporat într-un plan desenând o curbă pentru fiecare vârf care ocolește vârful și punctul de mijloc al fiecărei muchii adiacente, așa cum se arată în figură. Pentru orice muchie uv a graficului, șirurile pentru u și v se intersectează de două ori aproape de mijlocul muchiei uv și nu există alte intersecții, astfel încât intersecția unei perechi de șiruri reprezintă perechi adiacente de vârfuri în graficul plan original. Alternativ, prin teorema de împachetare a cercurilor , orice graf plan poate fi reprezentat ca o colecție de cercuri, dintre care două se intersectează dacă și numai dacă vârfurile corespunzătoare sunt adiacente. Aceste cercuri (cu punctele de început și de sfârșit alese pentru a face din cercul o curbă deschisă) dau reprezentarea graficului de șir a graficului plan dat. Chalopin, Gonçalves și Ochem ( Chalopin, Gonçalves, Ochem 2007 ) au demonstrat că orice graf plan are o reprezentare grafică cu șiruri în care fiecare pereche de șiruri are cel mult o intersecție, nu așa cum este descris mai sus. Conjectura lui Scheinerman , acum dovedită, este o afirmație și mai riguroasă că orice graf plan poate fi reprezentat ca un graf de intersecție a segmentului de linie. x Dacă toate muchiile unui grafic dat G sunt subdivizate , graficul rezultat este un grafic cu șiruri dacă și numai dacă G este plan. În special, subdiviziunea graficului complet K 5 prezentat în figură nu este un grafic cu șiruri, deoarece K 5 nu este plană [3] .
Orice grafic circular precum graficul intersecțiilor segmentelor de linie (coardele unui cerc) este, de asemenea, un grafic cu șiruri. Orice graf cordal poate fi reprezentat ca un graf cu șiruri - graficele cordale sunt grafice de intersecție ale subarborilor de copaci și se poate forma o reprezentare în șir a unui graf cordal prin încorporarea plană a arborelui corespunzător și înlocuirea fiecărui subarbore cu un șir care înconjoară marginile lui. subarborele.
Complementul grafic al oricărui grafic de comparabilitate este, de asemenea, un grafic cu șiruri [4] .
Ehrlich, Even și Tarjan ( Ehrlich, Even, Tarjan 1976 ) au arătat că calcularea numărului cromatic al unui grafic de șiruri este o problemă NP-hard. Kratochvil ( 1991a ) a descoperit că graficele cu șiruri formează o clasă închisă de minori generați, dar nu o clasă minoră închisă de grafice.
Orice grafic șir cu m muchii poate fi descompus în două submulțimi, fiecare submulțime fiind o fracțiune fixă a graficului complet, prin îndepărtarea muchiilor O ( m 3/4 log 1/2 m ). Rezultă că graficele cu șiruri fără clicuri , graficele cu șiruri care nu conțin subgrafe K t , t pentru orice constantă t , au muchii O ( n ) și au o extensie polinomială [5] [6] .