Semi-dynamic Orthogonal Drawings of Planar Graphs (Extended Abstract)

Bachl, Walter (2002) Semi-dynamic Orthogonal Drawings of Planar Graphs (Extended Abstract). In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 354-361 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_33).

Full text not available from this repository.

Abstract

We introduce a new approach to orthogonal drawings of planar graphs. We define invariants that are respected by every drawing of the graph. The invariants are the embedding together with relative positions of adjacent vertices. Insertions imply only minor changes of the invariants. This preserves the users mental map. Our technique is applicable to two-connected planar graphs with vertices of arbitrary size and degree. New vertices and edges can be added to the graph in O(log n) time. The algorithm produces drawings with at most m + f bends, where m and f are the number of edges and faces of the graph.

Item Type:Conference Paper
Additional Information:10.1007/3-540-36151-0_33
Classifications:M Methods > M.300 Dynamic / Incremental / Online
G Algorithms and Complexity > G.999 Others
M Methods > M.600 Planar
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.999 Others
P Styles > P.540 Planar
ID Code:321

Repository Staff Only: item control page

References

S.S. Bridgeman, J. Fanto, A. Garg, R. Tamassia, and L. Vismara. InteractiveGiotto: An algorithm for interactive orthogonal graph drawing. In Graph Drawing (GD 97), LNCS 1353, pages 303-308. Springer, 1997.

U. Brandes, M. Güdemann, and D. Wagner. Fully dynamic orthogonal graph layout for interactive systems. Technical report, Universität Konstanz, 2000.

T.C. Biedl and M. Kaufmann. Area-efficient static and incremental graph drawings. In Proc. European Symposium on Algorithms (ESA '97), Lecture Notes in Computer Science 1284, pages 37-52. Springer, 1997.

F.J. Brandenburg. Designing graph drawings by layout graph grammars. In Graph Drawing (GD 94), LNCS 894, pages 416-427. Springer, 1995.

G. Di Battista and R. Tamassia. On-line planarity testing. SIAM Journal on Computing, 25(5):956-997, 1996.

S.S. Bridgeman and R. Tamassia. Difference metrics for interactive orthogonal graph drawing algorithms. In Graph Drawing (GD 98), LNCS 1547, pages 57-71. Springer, 1998.

P. Eades, W. Lai, K. Misue, and K. Sugiyama. Preserving the mental map of a diagram. In Proceedings of Compugraphics '91, pages 24-33, 1991.

U. Fößmeier and M. Kaufmann. Drawing high degree graphs with low bend numbers. In Graph Drawing (GD 95), LNCS 1027, pages 254-266. Springer, 1996.

U. Fößmeier. Interactive orthogonal graph drawing: Algorithms and bounds. In Graph Drawing (GD 97), LNCS 1353, pages 111-123. Springer, 1997.

K. Misue, P. Eades, W. Lai, and K. Sugiyama. Layout adjustment and the mental map. Journal of visual languages and computing, 6:183-210, 1995.

A. Papakostas and I.G. Tollis. Issues in interactive orthogoanl graph drawing. In Graph Drawing (GD 95), LNCS 1027, pages 419-430. Springer, 1996.

F.P. Preparata and M.I. Shamos. Computational Geometry: An Introduction. Springer. 1985