Geodesic
Minimal Representations of Order Types by Geometric Graphs
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Twenty-seventh International Symposium on Graph Drawing and Network Visualization, GD 2019 , Tome 24 (2020) no. 4, pp. 551-572.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00545
Keywords: geometric graph, straight-line drawing, order type, pseudoline arrangement, triangular cell 
@article{JGAA_2020_24_4_a1,
     author = {Oswin Aichholzer and Martin Balko and Michael Hoffmann and Jan Kyn\v{c}l and Wolfgang Mulzer and Irene Parada and Alexander Pilz and Manfred Scheucher and Pavel Valtr and Birgit Vogtenhuber and Emo Welzl},
     title = {Minimal {Representations} of {Order} {Types} by {Geometric} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {551--572},
     publisher = {mathdoc},
     volume = {24},
     number = {4},
     year = {2020},
     doi = {10.7155/jgaa.00545},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00545/}
}
TY  - JOUR
AU  - Oswin Aichholzer
AU  - Martin Balko
AU  - Michael Hoffmann
AU  - Jan Kynčl
AU  - Wolfgang Mulzer
AU  - Irene Parada
AU  - Alexander Pilz
AU  - Manfred Scheucher
AU  - Pavel Valtr
AU  - Birgit Vogtenhuber
AU  - Emo Welzl
TI  - Minimal Representations of Order Types by Geometric Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2020
SP  - 551
EP  - 572
VL  - 24
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00545/
DO  - 10.7155/jgaa.00545
LA  - en
ID  - JGAA_2020_24_4_a1
ER  - 
%0 Journal Article
%A Oswin Aichholzer
%A Martin Balko
%A Michael Hoffmann
%A Jan Kynčl
%A Wolfgang Mulzer
%A Irene Parada
%A Alexander Pilz
%A Manfred Scheucher
%A Pavel Valtr
%A Birgit Vogtenhuber
%A Emo Welzl
%T Minimal Representations of Order Types by Geometric Graphs
%J Journal of Graph Algorithms and Applications
%D 2020
%P 551-572
%V 24
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00545/
%R 10.7155/jgaa.00545
%G en
%F JGAA_2020_24_4_a1
Oswin Aichholzer; Martin Balko; Michael Hoffmann; Jan Kynčl; Wolfgang Mulzer; Irene Parada; Alexander Pilz; Manfred Scheucher; Pavel Valtr; Birgit Vogtenhuber; Emo Welzl. Minimal Representations of Order Types by Geometric Graphs. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Twenty-seventh International Symposium on Graph Drawing and Network Visualization, GD 2019
					, Tome 24 (2020) no. 4, pp. 551-572. doi : 10.7155/jgaa.00545. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00545/

Cité par Sources :