 |
| Home | Issues | About JGAA | Instructions for Authors |
|
Special issue on Selected papers from the Twenty-seventh International Symposium on Graph Drawing and Network Visualization, GD 2019
DOI: 10.7155/jgaa.00545
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, and
Emo Welzl
Vol. 24, no. 4, pp. 551-572, 2020. Regular paper.
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.
|
Submitted: October 2019.
Reviewed: July 2020.
Revised: September 2020.
Reviewed: October 2020.
Revised: November 2020.
Accepted: November 2020.
Final: November 2020.
Published: December 2020.
|
Journal publisher
|
Journal network
|
Journal Supporters
|
