Home Issues About JGAA Instructions for Authors
 
 
Special Issue on Selected papers from the Twenty-third International Symposium on Graph Drawing and Network Visualization, GD 2015
DOI: 10.7155/jgaa.00402
Rook-drawings of Plane Graphs
Vol. 21, no. 1, pp. 103-120, 2017. Regular paper.
Abstract 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.
Submitted: November 2015.
Reviewed: April 2016.
Revised: May 2016.
Accepted: August 2016.
Final: September 2016.
Published: January 2017.
Communicated by Emilio Di Giacomo and Anna Lubiw
article (PDF)
BibTeX