Minimal representations of order types by geometric graphs

Oswin Aichholzer, Martin Balko, Michael Hoffmann, Jan Kyncl, Wolfgang Mulzer, Irene Parada, Alexander Pilz, Manfred Scheucher, Pavel Valtr, Birgit Vogtenhuber, Emo Welzl

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)551-572
Number of pages22
JournalJournal of Graph Algorithms and Applications
Issue number4
Publication statusPublished - Dec 2020

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computer Science(all)
  • Computer Science Applications
  • Computational Theory and Mathematics

Fields of Expertise

  • Information, Communication & Computing


Dive into the research topics of 'Minimal representations of order types by geometric graphs'. Together they form a unique fingerprint.

Cite this