TY - GEN
T1 - Fast spherical drawing of triangulations
T2 - 17th Symposium on Experimental Algorithms, SEA 2018
AU - Aleardi, Luca Castelli
AU - Denis, Gaspard
AU - Fusy, Éric
N1 - Publisher Copyright:
© Luca C. Aleardi, Gaspard Denis, and Éric Fusy; licensed under Creative Commons License CC-BY.
PY - 2018/6/1
Y1 - 2018/6/1
N2 - We consider the problem of computing a spherical crossing-free geodesic drawing of a planar graph: this problem, as well as the closely related spherical parameterization problem, has attracted a lot of attention in the last two decades both in theory and in practice, motivated by a number of applications ranging from texture mapping to mesh remeshing and morphing. Our main concern is to design and implement a linear time algorithm for the computation of spherical drawings provided with theoretical guarantees. While not being aesthetically pleasing, our method is extremely fast and can be used as initial placer for spherical iterative methods and spring embedders. We provide experimental comparison with initial placers based on planar Tutte parameterization. Finally we explore the use of spherical drawings as initial layouts for (Euclidean) spring embedders: experimental evidence shows that this greatly helps to untangle the layout and to reach better local minima.
AB - We consider the problem of computing a spherical crossing-free geodesic drawing of a planar graph: this problem, as well as the closely related spherical parameterization problem, has attracted a lot of attention in the last two decades both in theory and in practice, motivated by a number of applications ranging from texture mapping to mesh remeshing and morphing. Our main concern is to design and implement a linear time algorithm for the computation of spherical drawings provided with theoretical guarantees. While not being aesthetically pleasing, our method is extremely fast and can be used as initial placer for spherical iterative methods and spring embedders. We provide experimental comparison with initial placers based on planar Tutte parameterization. Finally we explore the use of spherical drawings as initial layouts for (Euclidean) spring embedders: experimental evidence shows that this greatly helps to untangle the layout and to reach better local minima.
KW - And phrases Graph drawing
KW - Planar triangulations
KW - Spherical parameterizations
UR - https://www.scopus.com/pages/publications/85063740216
U2 - 10.4230/LIPIcs.SEA.2018.24
DO - 10.4230/LIPIcs.SEA.2018.24
M3 - Conference contribution
AN - SCOPUS:85063740216
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 24:1-24:14
BT - 17th Symposium on Experimental Algorithms, SEA 2018
A2 - D'Angelo, Gianlorenzo
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 27 June 2018 through 29 June 2018
ER -