2016/06/07 by Thérèse Biedl, Biedl, Therese, Claire Pennarun +1
Computer Science · Engineering · #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Robotics and Sensor-Based Localization
paper · pdf · doi:10.48550/arxiv.1606.02220
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 non-aligned drawings that are straight-line, planar, and in the minimal-possible n× n-grid. They also showed that such drawings exist 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 in an n× n-grid with significantly fewer bends, and we study what grid-size can be achieved if we insist on having straight-line drawings.