Non-aligned Drawings of Planar Graphs

Bidl, Therese and Pennarun, Claire (2016) Non-aligned Drawings of Planar Graphs. In: Graph Drawing and Network Visualization. GD 2016, September, 19. - 21., 2016 , pp. 131-143(Official URL:

Full text not available from this repository.


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×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 in an n×n -grid with at most (2n−5)/3 bends, and we study what grid-size can be achieved if we insist on having straight-line drawings.

Item Type: Conference Paper
Classifications: P Styles > P.540 Planar
P Styles > P.720 Straight-line

Actions (login required)

View Item View Item