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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
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)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kornaropoulos, E.M., Tollis, I.G. (2012). Overloaded Orthogonal Drawings. In: van Kreveld, M., Speckmann, B. (eds) Graph Drawing. GD 2011. Lecture Notes in Computer Science, vol 7034. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25878-7_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-25878-7_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25877-0
Online ISBN: 978-3-642-25878-7
eBook Packages: Computer ScienceComputer Science (R0)