O diagramă cu arc este un stil de reprezentare grafică în care vârfurile sunt aranjate de-a lungul unei linii drepte pe planul euclidian , iar muchiile sunt desenate ca semicercuri pe unul dintre cele două semiplane sau ca curbe netede formate de semicercuri. În unele cazuri, segmentele de linie sunt, de asemenea, folosite pentru a reprezenta marginile graficului dacă conectează vârfuri adiacente pe linie.
Denumirea „diagrama arcului” pentru această reprezentare a graficelor este un succesor al utilizării unui tip similar de diagramă Wattenberg [1] , pe care a folosit-o pentru a vizualiza fragmente repetate de linii prin conectarea perechilor de subșiruri identice. Cu toate acestea, stilul reprezentării grafice în sine este mult mai vechi decât numele și datează din lucrările lui Saaty [2] și Nicholson [3] , care au folosit diagrame cu arc pentru a studia numărul de intersecție al graficelor . Un nume mai vechi, dar mai puțin folosit pentru diagramele cu arc este încorporarea liniilor [4] .
Heer, Bostock și Ogiwetsky [5] au scris că diagramele cu arc „nu pot exprima structura completă a unui grafic la fel de eficient ca o reprezentare bidimensională”, dar facilitează reprezentarea datelor multidimensionale asociate cu vârfurile graficului.
După cum a observat Nicholson [3] , orice încorporare a unui grafic într-un plan poate fi convertită într-o diagramă cu arc fără a modifica numărul de intersecții. În special, orice grafic plan are o diagramă cu arc planar. Cu toate acestea, o astfel de imbricare poate necesita utilizarea a mai mult de un semicerc pentru a desena unele dintre marginile graficului.
Dacă un grafic este desenat fără încrucișări de arc ca o diagramă de arc în care fiecare muchie este reprezentată printr-un singur semicerc, desenul este o încorporare a unei cărți de două pagini , ceea ce este posibil doar pentru graficele sub-Hamiltoniene , un subset de grafice plane [6] ] . De exemplu, un graf planar maximal are o astfel de încorporare dacă și numai dacă conține un ciclu hamiltonian . Astfel, un graf planar maximal non-Hamiltonian, cum ar fi graful Goldner-Harari , nu poate avea o încorporare plană cu un semicerc pe muchie. Verificarea dacă un grafic dat are o diagramă cu arc fără intersecții de acest tip (sau, echivalent, grosimea cărții graficului este de două) este o problemă NP-completă [7] .
Totuși, orice graf plan are o diagramă cu arc în care fiecare muchie este reprezentată ca un bi -arc , constând din cel mult două semicercuri. Mai strict, orice graf direcționat st -planar (graf aciclic direcționat plan cu o sursă și o singură absorbție, ambele pe fața exterioară) are o diagramă cu arc în care orice muchie formează o curbă monotonă, toate curbele (marginile) sunt direcționate în același direcția [8] . Pentru graficele plane nedirecționate, o modalitate de a construi o diagramă cu arc cu cel mult două semicercuri pe muchie este să împărțiți graficul și să adăugați mai multe muchii pentru a obține un ciclu hamiltonian (unde muchiile sunt împărțite în cel mult două părți), apoi utilizați ordinea de-a lungul ciclului hamiltonian ca ordinea vârfurilor pe o dreaptă [9] .
Deoarece verificarea dacă un grafic dat are o diagramă cu arc fără intersecții cu un semicerc pe muchie este o problemă NP-completă, este, de asemenea, o problemă dificilă NP să găsiți o diagramă cu arc care să minimizeze numărul de intersecții. Problema minimizării numărului de intersecții rămâne NP-hard pentru graficele neplanare, chiar dacă ordinea vârfurilor de-a lungul dreptei este deja dată [4] . Cu toate acestea, în cazul unei anumite ordine de vârfuri, o încorporare fără intersecție (dacă există una) poate fi găsită în timp polinomial prin conversia problemei într-o problemă de 2-satisfiability , unde variabilele reprezintă locația fiecărui arc. , iar constrângerile împiedică poziționarea a două muchii care se intersectează de-a lungul unei laturi a liniei cu vârfuri [10] . În plus, în cazul unei locații fixe de vârfuri, imbricarea cu minimizarea numărului de intersecții poate fi aproximată prin rezolvarea problemei tăieturii maxime într-un graf auxiliar care reprezintă semicercurile și intersecțiile potențiale ale acestora [11] .
Kimikowski, Shoup [12] [13] , He, Sikora și Wrto [14] au discutat despre algoritmi euristici pentru găsirea diagramelor de arc cu intersecții multiple.
Pentru a reprezenta grafice direcționate, convenția generală este de a direcționa arcele în sensul acelor de ceasornic, astfel încât arce de la stânga la dreapta să fie desenate deasupra liniei, iar arcele de la dreapta la stânga să fie desenate sub linie. Această convenție de orientare în sensul acelor de ceasornic a fost dezvoltată ca parte a unui alt stil de reprezentare grafică de către un grup care a inclus Fekete, Wang, Dang și Aris [15] , iar Pretorius și van Wijk [16] au aplicat acest stil diagramelor cu arc .
Diagramele cu arc au fost folosite de Brandes [17] pentru a vizualiza diagramele de stare a registrului de deplasare , iar de Jijev și Wrto [18] pentru a demonstra că numărul de intersecție al oricărui grafic este cel puțin egal cu pătratul lățimii sale tăiate.