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, Los Angeles, CA, USA , 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
ID Code:1487

Repository Staff Only: item control page


Abello, J., Van Ham, F., Krishnan, N.: ASK-GraphView: a large scale graph visualization system. IEEE Trans. Vis. Comput. Graph. 12(5), 669–676 (2006)

Andrews, G.E.: A lower bound for the volume of strictly convex bodies with many boundary lattice points. Trans. Am. Math. Soc. 106, 270–279 (1963)

Archambault, D., Purchase, H.C.: Mental map preservation helps user orientation in dynamic graphs. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 475–486. Springer, Heidelberg (2013)

Bonichon, N., Gavoille, C., Hanusse, N.: Canonical decomposition of outerplanar maps and application to enumeration, coding, and generation. J. Graph Algorithms Appl. 9(2), 185–204 (2005)

Bonichon, N., Le Saëc, B., Mosbah, M.: Optimal area algorithm for planar polyline drawings. In: Kučera, L. (ed.) WG 2002. LNCS, vol. 2573, pp. 35–46. Springer, Heidelberg (2002)

Bose, P.: On embedding an outerplanar graph in a point set. Comput. Geom. 23(3), 303–312 (2002)

Di Giacomo, E., Didimo, W., Kaufmann, M., Liotta, G., Montecchiani, F.: Upward-rightward planar drawings. In: The 5th International Conference on Information, Intelligence, Systems and Applications, IISA 2014, pp. 145–150. IEEE (2014)

Eades, P., Feng, Q.-W.: Multilevel visualization of clustered graphs. In: North, S.C. (ed.) GD 1996. LNCS, vol. 1190, pp. 101–112. Springer, Heidelberg (1997)

de Fraysseix, H., Pach, J., Pollack, R.: Small sets supporting fary embeddings of planar graphs. In: Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 426–433. ACM (1988)

Kornaropoulos, E.M., Tollis, I.G.: Overloaded orthogonal drawings. In: Speckmann, B. (ed.) GD 2011. LNCS, vol. 7034, pp. 242–253. Springer, Heidelberg (2011)

Kornaropoulos, E.M., Tollis, I.G.: DAGView: an approach for visualizing large graphs. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 499–510. Springer, Heidelberg (2013)

Misue, K., Eades, P., Lai, W., Sugiyama, K.: Layout adjustment and the mental map. J. Visual Lang. Comput. 6(2), 183–210 (1995)

Pach, J., Gritzmann, P., Mohar, B., Pollack, R.: Embedding a planar triangulation with vertices at specified points. Am. Math. Monthly 98, 165–166 (1991)

Schnyder, W.: Embedding planar graphs on the grid. Symp. Discrete Algorithms 90, 138–148 (1990)