We introduce a new type of graph drawing called "rook-drawing". A rook-drawing of a graph $G$ is obtained by placing the $n$ nodes of $G$ on the intersections of a regular grid, such that each row and column of the grid supports exactly one node. This paper focuses on rook-drawings of planar graphs. We first give a linear algorithm to compute a planar straight-line rook-drawing for outerplanar graphs. We then characterize the maximal planar graphs admitting a planar straight-line rook-drawing, which are unique for a given order. Finally, we give a linear time algorithm to compute a polyline planar rook-drawing for plane graphs with at most $n-3$ bent edges.
展开▼
机译：我们介绍一种称为“ rook-drawing”的新型图形。通过将$ G $的$ n $个节点放置在规则网格的交点上，可以得到图形$ G $的车前图。本文着重于平面图的白描图。我们首先给出一个线性算法来计算外平面图的平面直线白描。然后，我们表征允许平面直线白描的最大平面图，这对于给定的顺序是唯一的。最后，我们给出了线性时间算法，以计算最多具有$ n-3 $弯曲边的平面图的折线平面流向绘图。
展开▼
