Minimal representations of order types by geometric graphs

O. Aichholzer, M. Balko, M. Hoffmann, J. Kyncl, W. Mulzer, I. Parada, A. Pilz, M. Scheucher, P. Valtr, B. Vogtenhuber, and E. Welzl

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 unequivocally display exit edges, which prevent the order type from changing under continuous motion of vertices. Exit edges have a natural dual characterization, which allows us to efficiently compute them and to bound their number.

Reference: O. Aichholzer, M. Balko, M. Hoffmann, J. Kyncl, W. Mulzer, I. Parada, A. Pilz, M. Scheucher, P. Valtr, B. Vogtenhuber, and E. Welzl. Minimal representations of order types by geometric graphs. In Graph Drawing and Network Visualization. GD 2019, volume 11904 of Lecture Notes in Computer Science (LNCS), pages 101-113, Prague, Czechia, 2019.