Special issue on Selected papers from the Twenty-seventh International Symposium on Graph Drawing and Network Visualization, GD 2019
Minimal Representations of Order Types by Geometric Graphs
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.
Communicated by Daniel Archambault and Csaba D. Tóth
article (PDF)