Minimal Representations of Order Types by Geometric Graphs

Abstract

In order to have a compact visualization of the order type of a given point set $S$, we are interested in geometric graphs on $S$ with few edges that unambiguously display the order type of $S$. We introduce the concept of exit edges, which prevent the order type from changing under continuous motion of vertices. That is, in the geometric graph on $S$ whose edges are the exit edges, in order to change the order type of $S$, at least one vertex needs to move across an exit edge. Exit edges have a natural dual characterization, which allows us to efficiently compute them and to bound their number.