Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00506
How to Draw a Planarization
Vol. 23, no. 4, pp. 653-682, 2019. Regular paper.
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 ${\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.
|
Submitted: January 2019.
Reviewed: March 2019.
Revised: May 2019.
Accepted: July 2019.
Final: July 2019.
Published: September 2019.
Communicated by
Giuseppe Liotta
|
Journal Supporters
|