RookDrawing for Plane GraphsAuber, David and Bonichon, Nicolas and Dorbec, Paul and Pennarun, Claire (2015) RookDrawing for Plane Graphs. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 2426, 2015 , pp. 180191(Official URL: http://dx.doi.org/10.1007/9783319272610_15). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319272610_15
AbstractMotivated by visualization of large graphs, we introduce a new type of graph drawing called “rookdrawing”. A rookdrawing 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 rookdrawings of planar graphs. We first give a linear algorithm to compute a planar straightline rookdrawing for outerplanar graphs. We then characterize the maximal planar graphs admitting a planar straightline rookdrawing, which are unique for a given order. Finally, we give a linear time algorithm to compute a polyline planar rookdrawing for plane graphs with at most n−3 bent edges.
Actions (login required)
