Zichtbaarheidsgraaf (visibility graph)
Een graaf waarvan de knopen hoeken van obstakels zijn en waarvan de bogen hoeken verbinden die elkaar kunnen zien; het kortste pad erdoorheen is het kortste pad langs de obstakels.
Geïntroduceerd door Tomás Lozano-Pérez en Michael Wesley in 1979 voor bewegingsplanning van robots. Omdat een kortste pad in een vlak vol veelhoekige obstakels altijd rechtlijnig tussen obstakelhoeken loopt, volstaat het om de graaf uit die hoeken op te bouwen en er A* of Dijkstra overheen te laten lopen.
Het pad schuurt strak langs de hoeken, wat natuurlijk oogt maar een marge kan vereisen zodat eenheden niet langs de muur schrapen. In complexe 3D-omgevingen heeft de navmesh het grotendeels overgenomen, maar in 2D leeft de zichtbaarheidsgraaf voort.