I beregningsgeometri og bevægelsesplanlægning robotter , er en synlighedsgraf en graf over gensidig synlighed af punkter i rummet, normalt for et sæt punkter og forhindringer på det euklidiske plan . Ethvert toppunkt i grafen repræsenterer et punkt i rummet, og enhver kant repræsenterer sigtelinje mellem punkter. Det vil sige, at hvis et lige linjestykke, der forbinder to punkter i rummet, ikke passerer gennem nogen forhindring, vil der blive tegnet en kant i grafen. Hvis sættet af punkter i rummet ligger på en linje, kan de forstås som en ordnet sekvens. Synlighedsgrafer strækker sig således ind i tidsserieanalyses domæne .
Sigtbarhedsgrafer kan bruges til at finde korteste veje blandt polygonale forhindringer i et plan - den korteste vej mellem to forhindringer er i en lige linje og drejer i hjørnerne af forhindringerne, så den korteste vej er den korteste vej i sigtbarheden graf, hvis toppunkter er start- og slutpunkter og toppen af forhindringer [1] [2] . Således kan det korteste vejproblem opdeles i to enklere problemer - at bygge en synlighedsgraf og anvende en korteste vejalgoritme som Dijkstras algoritme på grafen . For at planlægge bevægelsen af en robot, der har en mærkbar størrelse i forhold til forhindringerne, kan en lignende tilgang bruges ved at øge forhindringerne for at kompensere for størrelsen af robotten [1] [2] . Lozano-Peretz og Wesley [2] tilskriver synlighedsgrafmetoden for den korteste vej på det euklidiske plan til en undersøgelse fra 1969 af Nils Nilsson om planlægning af Sheka-robottens bevægelse og citerer en beskrivelse af denne metode i 1973 af russiske matematikere M. B. Ignatiev , F. M. Kulakov og A. M. Pokrovsky.
Synlighedsgrafer kan også bruges til at beregne positionen af radioantenner eller som et værktøj i arkitektur og byplanlægning i analysen af synlighed .
Hvis mængden af rumpunkter ligger på en ret linje, kan de forstås som en ordnet sekvens [3] . Dette specielle tilfælde bygger bro mellem tidsserier , dynamiske systemer og grafteori .
Synlighedsgrafen for en simpel polygon (dvs. uden krydsende sider) har toppunkterne som punkter i rummet og det ydre område af polygonen som en hindring. Synlighedsgraferne for simple polygoner skal være Hamiltonske - grænsen for en polygon danner en Hamiltonsk cyklus i synlighedsgrafen. Det er kendt, at ikke alle synlighedsgrafer danner en simpel polygon. Faktisk har synlighedsgrafer for simple polygoner ikke karakteristika for nogen klasse af grafer [4] .
Billedgalleriproblemet er problemet med at finde et lille sæt punkter, så alle andre punkter er synlige fra punkter i dette sæt. Nogle former for kunstgalleriproblemet kan tolkes som at finde et dominerende sæt i en synlighedsgraf.
Bitangente systemer af polygoner eller kurver er linjer, der tangerer to polygoner. Bitangente sæt af polygoner danner en delmængde af synlighedsgrafen, der har polygonhjørnepunkter som grafhjørnepunkter (punkter i rummet), hvor polygoner tjener som forhindringer. Synlighedsgrafen for problemet med at finde den korteste vej kan forbedres ved at danne bitangenter i stedet for alle synlighedskanter, da den korteste vej kun kan passere langs bitangenter [5] .