Ve výpočetní geometrii a plánování pohybu robotů je graf viditelnosti grafem vzájemné viditelnosti bodů v prostoru, obvykle pro soubor bodů a překážek na euklidovské rovině . Jakýkoli vrchol v grafu představuje bod v prostoru a jakákoli hrana představuje linii pohledu mezi body. To znamená, že pokud úsečka spojující dva body v prostoru neprochází žádnou překážkou, vykreslí se do grafu hrana. Pokud množina bodů v prostoru leží na přímce, lze je chápat jako uspořádanou posloupnost. Grafy viditelnosti tak zasahují do oblasti analýzy časových řad .
Grafy viditelnosti lze použít k nalezení nejkratších cest mezi polygonálními překážkami v rovině - nejkratší cesta mezi dvěma překážkami je přímá a otáčí se ve vrcholech překážek, takže nejkratší cesta je nejkratší cesta ve viditelnosti graf, jehož vrcholy jsou počáteční a koncové body a vrcholy překážek [1] [2] . Problém nejkratší cesty lze tedy rozdělit na dva jednodušší problémy – sestavení grafu viditelnosti a aplikace algoritmu nejkratší cesty, jako je Dijkstrův algoritmus , na graf . K plánování pohybu robota, který má ve srovnání s překážkami znatelnou velikost, lze použít podobný přístup zvětšením překážek, aby se kompenzovala velikost robota [1] [2] . Lozano-Peretz a Wesley [2] připisují metodu grafu viditelnosti pro nejkratší cestu na euklidovské rovině studii Nilse Nilssona o plánování pohybu robota Sheka z roku 1969 a citují popis této metody v roce 1973 ruskými matematiky M. B. Ignatievem. , F. M. Kulakov a A. M. Pokrovsky.
Grafy viditelnosti lze také použít k výpočtu polohy rádiových antén nebo jako nástroj v architektuře a urbanismu při analýze viditelnosti .
Leží-li množina prostorových bodů na přímce, lze je chápat jako uspořádanou posloupnost [3] . Tento speciální případ staví most mezi časovými řadami , dynamickými systémy a teorií grafů .
Graf viditelnosti jednoduchého mnohoúhelníku (tj. bez křížení stran) má vrcholy jako body v prostoru a vnější oblast mnohoúhelníku jako překážku. Grafy viditelnosti jednoduchých polygonů musí být hamiltonovské — hranice polygonu tvoří v grafu viditelnosti hamiltonovský cyklus. Je známo, že ne všechny grafy viditelnosti tvoří jednoduchý mnohoúhelník. Ve skutečnosti grafy viditelnosti jednoduchých polygonů nemají vlastnosti žádné třídy grafů [4] .
Problém galerie obrázků je problém najít malou sadu bodů tak, aby všechny ostatní body byly viditelné z bodů v této sadě. Některé formy problému umělecké galerie lze interpretovat jako nalezení dominantního souboru v grafu viditelnosti.
Bitangentní systémy polygonů nebo křivek jsou čáry, které jsou tečné ke dvěma polygonům. Bitangentní sady polygonů tvoří podmnožinu grafu viditelnosti, která má vrcholy polygonů jako vrcholy grafu (body v prostoru), polygony sloužící jako překážky. Graf viditelnosti pro problém nalezení nejkratší cesty lze zlepšit vytvořením bitangentů namísto všech hran viditelnosti, protože nejkratší cesta může procházet pouze podél bitangent [5] .