Geodesic
How to Draw a Planarization
Journal of Graph Algorithms and Applications, Tome 23 (2019) no. 4, pp. 653-682.

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

We study the problem of computing straight-line drawings of non-planar graphs with few crossings. We assume that a crossing-minimization algorithm is applied first, yielding a planarization, i.e., a planar graph with a dummy vertex for each crossing, that fixes the topology of the resulting drawing. We present and evaluate two different approaches for drawing a planarization in such a way that the edges of the input graph are as straight as possible. The first approach is based on the planarity-preserving force-directed algorithm ${\rm I{\small M}P{\small R}E{\small D}}$ [Simonetto et al. Computer Graphics Forum 2011], the second approach, which we call Geometric Planarization Drawing, iteratively moves vertices to their locally optimal positions in the given initial drawing. Our evaluation shows that both approaches significantly improve the initial drawing and that our geometric approach outperforms the force-directed approach. To the best of our knowledge, this is the first paper concerned with the generation of a straight-line drawing that respects an arbitrary planarization.
DOI : 10.7155/jgaa.00506
Keywords: crossing minimization, stretchability, straight-line drawings, geometric drawings, planarization, experiments 
@article{JGAA_2019_23_4_a2,
     author = {Thomas Bl\"asius and Marcel Radermacher and Ignaz Rutter},
     title = {How to {Draw} a {Planarization}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {653--682},
     publisher = {mathdoc},
     volume = {23},
     number = {4},
     year = {2019},
     doi = {10.7155/jgaa.00506},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00506/}
}
TY  - JOUR
AU  - Thomas Bläsius
AU  - Marcel Radermacher
AU  - Ignaz Rutter
TI  - How to Draw a Planarization
JO  - Journal of Graph Algorithms and Applications
PY  - 2019
SP  - 653
EP  - 682
VL  - 23
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00506/
DO  - 10.7155/jgaa.00506
LA  - en
ID  - JGAA_2019_23_4_a2
ER  - 
%0 Journal Article
%A Thomas Bläsius
%A Marcel Radermacher
%A Ignaz Rutter
%T How to Draw a Planarization
%J Journal of Graph Algorithms and Applications
%D 2019
%P 653-682
%V 23
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00506/
%R 10.7155/jgaa.00506
%G en
%F JGAA_2019_23_4_a2
Thomas Bläsius; Marcel Radermacher; Ignaz Rutter. How to Draw a Planarization. Journal of Graph Algorithms and Applications, Tome 23 (2019) no. 4, pp. 653-682. doi : 10.7155/jgaa.00506. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00506/

Cité par Sources :