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

doi:10.7155/jgaa.00545

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 journal › Article › peer-review

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.

Original language	English
Pages (from-to)	551-572
Number of pages	22
Journal	Journal of Graph Algorithms and Applications
Volume	24
Issue number	4
DOIs	https://doi.org/10.7155/jgaa.00545
Publication status	Published - Dec 2020

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
General Computer Science
Computer Science Applications
Computational Theory and Mathematics

Fields of Expertise

Information, Communication & Computing

Access to Document

10.7155/jgaa.00545Licence: CC BY 4.0

Cite this

@article{64d6f86a6d2b4a579c9a652747d04c39,

title = "Minimal representations of order types by geometric graphs",

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.",

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

note = "special issue of the 27th International Symposium on Graph Drawing and Network Visualization GD$$2019",

year = "2020",

month = dec,

doi = "10.7155/jgaa.00545",

language = "English",

volume = "24",

pages = "551--572",

journal = "Journal of Graph Algorithms and Applications ",

publisher = "Brown University",

number = "4",

}

TY - JOUR

T1 - Minimal representations of order types by geometric graphs

AU - Aichholzer, Oswin

AU - Balko, Martin

AU - Hoffmann, Michael

AU - Kyncl, Jan

AU - Mulzer, Wolfgang

AU - Parada, Irene

AU - Pilz, Alexander

AU - Scheucher, Manfred

AU - Valtr, Pavel

AU - Vogtenhuber, Birgit

AU - Welzl, Emo

N1 - special issue of the 27th International Symposium on Graph Drawing and Network Visualization GD$$2019

PY - 2020/12

Y1 - 2020/12

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85098050958&partnerID=8YFLogxK

U2 - 10.7155/jgaa.00545

DO - 10.7155/jgaa.00545

M3 - Article

VL - 24

SP - 551

EP - 572

JO - Journal of Graph Algorithms and Applications

JF - Journal of Graph Algorithms and Applications

IS - 4

ER -

Minimal representations of order types by geometric graphs

Abstract

ASJC Scopus subject areas

Fields of Expertise

Access to Document

Other files and links

Fingerprint

Cite this