Overloaded Orthogonal Drawings

Kornaropoulos, Evgenios M. and Tollis, Ioannis G. (2012) Overloaded Orthogonal Drawings. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 242-253 (Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_24).

Full text not available from this repository.

Abstract

Orthogonal drawings are widely used for graph visualization due to their high clarity of representation. In this paper we present a technique called Overloaded Orthogonal Drawing. We first place the vertices on grid points following a relaxed version of dominance drawing, called weak dominance condition. Edge routing is implied automatically by the vertex coordinates. In order to simplify these drawings we use an overloading technique. All algorithms are simple and easy to implement and can be applied to directed acyclic graphs, planar, non-planar and also undirected graphs. We also present bounds on the number of bends and the area. Overloaded Orthogonal drawings present several interesting properties such as efficient visual edge confirmation as well as simplicity and clarity of the drawing.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_24
Classifications:P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:1259

Repository Staff Only: item control page

References

Bertolazzi, P., Di Battista, G., Didimo, W.: Computing orthogonal drawings with the minimum number of bends. IEEE Transactions on Computers 49(8), 826–840 (2000)

Biedl, T., Kant, G.: A better heuristic for orthogonal graph drawings. Computational Geometry: Theory and Applications 9(3), 159–180 (1998)

Biedl, T.C., Madden, B.P., Tollis, I.G.: The Three-Phase Method: A Unified Approach to Orthogonal Graph Drawing. Int. J. Comput. Geometry Appl. 10(6), 553–580 (2000)

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of graphs. Prentice - Hall, New Jersey (1998)

Di Battista, G., Tamassia, R., Tollis, I.G.: Area Requirement and Symmetry Display of Planar Upward Drawings. Discrete and Comput. Geom. 7(4), 381–401 (1992)

Dickerson, M., Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent Drawings: Vizualizing Non-planar Diagrams in a Planar Way. Journal of Graph Algorithms and Applications 9(1), 31–52 (2005)

Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent Layered Drawings. Algorithmica 47(4), 439–452 (2007)

Even, S., Tarjan, R.: Computing an st-numbering. Theoretical Computer Science 2(3), 339–344 (1976)

Fößmeier, U., Kaufmann, M.: Algorithms and Area Bounds for Nonplanar Orthogonal Drawings. In: DiBattista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 134–145. Springer, Heidelberg (1997)

Kornaropoulos, E.M., Tollis, I.G.: Weak Dominance Drawings and Linear Extension Diameter, arXiv:1108.1439 (2011)

Lengauer, T.: Combinatorial algorithms for integrated circuit layout. John Wiley & Sons, Inc., New York (1990)

Nomura, K., Tayu, S., Ueno, S.: On the Orthogonal Drawing of Outerplanar Graphs. Journal IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E88-A(6), 1583–1588 (2005)

Papakostas, A., Tollis, I.G.: Efficient Orthogonal Drawings of High Degree Graphs. Algorithmica 26(1), 100–125 (2000)

Papakostas, A., Tollis, I.G.: Algorithms for Area-Efficient Orthogonal Drawings. Computational Geometry Theory and Applications 9(1-2), 83–110 (1998)

Papamanthou, C., Tollis, I.G.: Algorithms for computing a parameterized st-orientation. Theoretical Computer Science 408(2-3), 224–240 (2008)

Papamanthou, C., Tollis, I.G.: Applications of Parameterized st-Orientations. Journal of Graph Algorithms and Applications 14(2), 337–365 (2010)

Rahman, S., Nishizeki, T., Naznin, M.: Orthogonal Drawings of Plane Graphs Without Bends. Journal of Graph Algorithms and Applications 7(4), 335–362 (2003)

Storer, J.: On minimal node-cost planar embeddings. Networks 14(2), 181–212 (1984)

Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. Computing 16(3), 421–444 (1987)

Tamassia, R., Tollis, I.G.: Planar Grid Embeddings in Linear Time. IEEE Transactions on Circuits and Systems 36(9), 1230–1234 (1989)

Vismara, L., Di Battista, G., Garg, A., Liotta, G., Tamassia, R., Vargiu, F.: Experimental studies on graph drawing algorithms. Software: Practice and Experience 30(11), 1235–1284 (2000)