Minimal Representations of Order Types by Geometric Graphs

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-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 unequivocally 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. Exit edges have a natural dual characterization, which allows us to efficiently compute them and to bound their number.
Original languageEnglish
Title of host publicationGraph Drawing and Network Visualization
Subtitle of host publication27th International Symposium, GD 2019, Prague, Czech Republic, September 17–20, 2019, Proceedings
Place of PublicationCham
ISBN (Electronic)978-3-030-35802-0
ISBN (Print)978-3-030-35801-3
Publication statusPublished - 2019
Event27th International Symposium on Graph Drawing and Network Visualization: GD 2019 - Hotel Floret, Pruhonice, Czech Republic
Duration: 17 Sept 201920 Sept 2019

Publication series

NameLecture Notes in Computer Science


Conference27th International Symposium on Graph Drawing and Network Visualization
Abbreviated titleGD 2019
Country/TerritoryCzech Republic
Internet address

Cite this