Rook-Drawing for Plane Graphs

Auber, David and Bonichon, Nicolas and Dorbec, Paul and Pennarun, Claire (2015) Rook-Drawing for Plane Graphs. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015 , pp. 180-191(Official URL:

Full text not available from this repository.


Motivated by visualization of large graphs, 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.

Item Type: Conference Paper
Classifications: M Methods > M.600 Planar
P Styles > P.540 Planar
P Styles > P.720 Straight-line
P Styles > P.999 Others
Z Theory > Z.750 Topology
Depositing User: Administration GDEA
Date Deposited: 04 May 2016 16:13
Last Modified: 04 May 2016 16:13

Actions (login required)

View Item View Item