Minimal Geometric Graph Representations of Order Types

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

Abstract:

We consider the problem of characterizing small geometric graphs whose structure uniquely determines the order type of its vertex set. We describe a set of edges that prevent the order type from changing by continuous movement and identify properties of the resulting graphs.

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 geometric graph representations of order types. In Proc. $34^{th}$ European Workshop on Computational Geometry EuroCG '18, pages 21:1-21:6, Berlin, Germany, 2018.