Home | Issues | About JGAA | Instructions for Authors |
Special issue on Selected papers from the Twenty-fourth International Symposium on Graph Drawing and Network Visualization, GD 2016
DOI: 10.7155/jgaa.00444
Non-aligned Drawings of Planar Graphs
Vol. 21, no. 5, pp. 915-937, 2017. Regular paper.
Abstract A non-aligned drawing of a graph is a drawing
where no two vertices are in the same row or column.
Auber et al. showed that not all planar graphs
have a non-aligned planar straight-line drawing in the $n\times n$-grid.
They also showed that such a drawing exists if up to $n-3$ edges may have a bend.
In this paper, we give algorithms for non-aligned planar drawings
that improve on the results by Auber et al. In particular, we
give such drawings on an $n\times n$-grid with
at most $\frac{2n-5}{3}$ bends, and we study what grid-size can be
achieved if we insist on having straight-line drawings.
|
Submitted: November 2016.
Reviewed: March 2017.
Revised: April 2017.
Accepted: June 2017.
Final: June 2017.
Published: October 2017.
|
Journal Supporters
|