Generalizing the Shift Method for Rectangular Shaped Vertices with Visibility Constraints

Hong, Seok-Hee and Mader, Martin, Martin (2009) Generalizing the Shift Method for Rectangular Shaped Vertices with Visibility Constraints. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 278-283 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_26).

Full text not available from this repository.

Abstract

In this paper we present a generalization of the shift method algorithm to obtain a straight-line grid drawing of a triconnected graph, where vertex representations have a certain specified size. We propose vertex representations having a rectangular shape. Additionally, one may demand maintainance of the criterion of strong visibility, that is, any possible line segment connecting two adjacent vertices cannot cross another vertex’ representation. We prove that the proposed method produces a straight-line grid drawing of a graph in linear time with an area bound, that is only extended by the size of the rectangles, compared to the bound of the original algorithm.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_26
Classifications:P Styles > P.720 Straight-line
ID Code:913

Repository Staff Only: item control page

References

Barequet, G., Goodrich, M.T., Riley, C.: Drawing planar graphs with large vertices and thick edges. J. Graph Algorithms Appl. 8, 3–20 (2004)

Battista,G.D., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall (1999)

Chrobak, M., Payne, T.H.: A linear-time algorithm for drawing a planar graph on a grid. Information Processing Letters 54(4), 241–246 (1995)

de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)

Harel, D., Sardas, M.: An algorithm for straight-line drawing of planar graphs. Algorithmica 20(2), 119–135 (1998)

Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16(1), 4–32 (1996)

Kaufmann, M., Wagner, D.(eds.): Drawing graphs: Methods and Models. Springer-Verlag, London, UK (2001)

Mader, M., Hong, S.: Drawing planar clustered graphs in 2.5 dimensions. Tech. rep., NICTA (2007), http://www.cs.usyd.edu.au/∼visual/valacon/

Nishizeki, T., Rahman, S.: Planar Graph Drawing, Lecture Note Series on Computing, vol.12. World Scientific, Singapore (2004)