Minimal Representations of Order Types by Geometric Graphs

Authors

  • Oswin Aichholzer
  • Martin Balko
  • Michael Hoffmann
  • Jan Kynčl
  • Wolfgang Mulzer
  • Irene Parada
  • Alexander Pilz
  • Manfred Scheucher
  • Pavel Valtr
  • Birgit Vogtenhuber
  • Emo Welzl

DOI:

https://doi.org/10.7155/jgaa.00545

Keywords:

geometric graph , straight-line drawing , order type , pseudoline arrangement , triangular cell

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.

Downloads

Download data is not yet available.

Downloads

Published

2020-12-01

How to Cite

Aichholzer, O., Balko, M., Hoffmann, M., Kynčl, J., Mulzer, W., Parada, I., … Welzl, E. (2020). Minimal Representations of Order Types by Geometric Graphs. Journal of Graph Algorithms and Applications, 24(4), 551–572. https://doi.org/10.7155/jgaa.00545