Search Results

Documents authored by Aleardi, Luca Castelli


Document
Fast Spherical Drawing of Triangulations: An Experimental Study of Graph Drawing Tools

Authors: Luca Castelli Aleardi, Gaspard Denis, and Éric Fusy

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)


Abstract
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.

Cite as

Luca Castelli Aleardi, Gaspard Denis, and Éric Fusy. Fast Spherical Drawing of Triangulations: An Experimental Study of Graph Drawing Tools. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{aleardi_et_al:LIPIcs.SEA.2018.24,
  author =	{Aleardi, Luca Castelli and Denis, Gaspard and Fusy, \'{E}ric},
  title =	{{Fast Spherical Drawing of Triangulations: An Experimental Study of Graph Drawing Tools}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.24},
  URN =		{urn:nbn:de:0030-drops-89597},
  doi =		{10.4230/LIPIcs.SEA.2018.24},
  annote =	{Keywords: Graph drawing, planar triangulations, spherical parameterizations}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail