Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00506
How to Draw a Planarization
Vol. 23, no. 4, pp. 653682, 2019. Regular paper.
Abstract We study the problem of computing straightline drawings of
nonplanar graphs with few crossings. We assume that a
crossingminimization 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 planaritypreserving
forcedirected 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 forcedirected approach. To the best of our
knowledge, this is the first paper concerned with the generation of
a straightline 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
