Visibility Graphs of Terrains

27^th April 2023, 15:00 EEE 6.05
Malte Renken

Abstract

Terrains are x-monotonous polygonal chains in the plane. Studying the line-of-sight connections between different points on the terrain gives

rise to several closely related graph classes. We look at some surprising connections these graphs have to the cyclic polytope and Dumont permutations, as well as at the structure of shortest paths in them.

Joint work with Vincent Froese.