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 x 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 x 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.
展开▼
机译：图的非对齐图是图形的图形，其中没有两个顶点位于同一行或列中。 Auber等。表明，并非所有平面图都具有N X N-Grid中的非对齐平面直线图。他们还表明，如果高达N - 3边缘可能具有弯曲，则存在这样的图形。在本文中，我们为不结对齐的平面图提供了改进Auber等人的结果的算法。特别是，我们在N X N-GRID中具有最多（2N-5）/ 3弯曲的图纸，我们研究了如果我们坚持具有直线图，可以实现哪些网格尺寸。
展开▼
