Abstract
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 ImPrEd [18], the second approach, which we call Geometric Planarization Drawing, iteratively moves vertices to their locally optimal positions in the given initial drawing.
This work was initiated within the FYS Heuristische Verfahren zur Visualisierung von dynamischen Netzwerken, financially supported by the “Concept for the Future” of KIT within the framework of the German Excellence Initiative. Work was partially supported by grant WA 654/21-1 of the German Research Foundation (DFG).
| Original language | English |
|---|---|
| Title of host publication | SOFSEM 2017: Theory and Practice of Computer Science |
| Subtitle of host publication | 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, January 16-20, 2017, Proceedings |
| Editors | Christel Baier, Mark van den Brand, Johann Eder, Mike Hinchey, Tiziana Margaria, Bernhard Steffen |
| Place of Publication | Dordrecht |
| Publisher | Springer |
| Pages | 295-308 |
| Number of pages | 14 |
| ISBN (Print) | 978-3-319-51963-0 |
| DOIs | |
| Publication status | Published - 2017 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 10139 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |