Article

Free access

Flexible layering in hierarchical drawings with nodes of arbitrary size

Authors:

Carsten Friedrich,

Falk SchreiberAuthors Info & Claims

ACSC '04: Proceedings of the 27th Australasian conference on Computer science - Volume 26

Pages 369 - 376

Published: 01 January 2004 Publication History

Abstract

Graph drawing is an important area of information visualization which concerns itself with the visualization of relational data structures. Relational data like networks, hierarchies, or database schemas can be modelled by graphs and represented visually using graph drawing algorithms. Most existing graph drawing algorithms do not consider the size of nodes when creating a drawing. In most real world applications, however, nodes contain information which has to be displayed and nodes thus need a specific area to display this information. The required area can vary significantly between different nodes in the same graph. In this paper we present an algorithm for the layering step of hierarchical graph drawing methods that is able to take the sizes of the nodes into account. It further allows the user to choose between compact drawings with many temporary (dummy) nodes and less compact drawings with fewer dummy nodes. A large number of dummy nodes can significantly increase the running time of the subsequent steps of hierarchical graph drawing methods.

References

[1]

Batini, C., Furlani, L. & Nardelli, E. (1985), What is a Good Diagram? A Pragmatic Approach, in 'Proc. of the 4th Intl. Conf. on Entity-Relationship Approach', pp. 312--319.]]

Digital Library

[2]

Biedl, T. C., Madden, B. P. & Tollis, I. G. (1997), The Three-Phase Method: A Unified Approach to Orthogonal Graph Drawing, in G. Di Battista, ed., 'Proc. of the 5th Intl. Symp. on Graph Drawing (GD'97)', Vol. 1353 of LNCS, Springer-Verlag, pp. 391--402.]]

Digital Library

[3]

Bloesch, A. (1993), 'Aesthetic Layout of Generalized Trees', Software - Practice and Experience23(8), 817--827.]]

Digital Library

[4]

Carpano, M.-J. (1980), 'Automatic Display for Hierarchized Graphs for Computer-Aided Decision Analysis', IEEE Trans. on Systems, Man, and Cybernetics10(11), 705--715.]]

[5]

Di Battista, G., Didimo, W., Patrignani, M. & Pizzonia, M. (1999), Orthogonal and Quasi-Upward Drawings with Vertices of Arbitrary Size, in J. Kratochvil, ed., 'Proc. of the 7th Intl. Symp. on Graph Drawing (GD'99)', Vol. 1731 of LNCS, Springer-Verlag, pp. 297--310.]]

[6]

Di Battista, G., Eades, P., Tamassia, R. & Tollis, I. G. (1999), Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, New Jersey.]]

Digital Library

[7]

Dobkin, D. P., Gansner, E. R., Koutsofios, E. & North, S. C. (1997), Implementing a General-Purpose Edge Router, in G. Di Battista, ed., 'Proc. of the 5th Intl. Symp. on Graph Drawing (GD'97)', Vol. 1353 of LNCS, Springer-Verlag, pp. 262--271.]]

Digital Library

[8]

Eades, P. (1984), 'A Heuristic for Graph Drawing', Congressus Numerantium42, 149--160.]]

[9]

Forster, M., Pick, A., Raitner, M., Schreiber, F. & Brandenburg, F. J. (2002), 'The system architecture of the BioPath system', In Silico Biology2(3), 415--426.]]

[10]

Fößmeier, U. & Kaufmann, M. (1997), Algorithms and Area Bounds for Nonplanar Orthogonal Drawings, in G. Di Battista, ed., 'Proc. of the 5th Intl. Symp. on Graph Drawing (GD'97)', Vol. 1353 of LNCS, Springer-Verlag, pp. 134--145.]]

Digital Library

[11]

Gansner, E. R., Koutsofios, E., North, S. C. & Vo, K. P. (1993), 'A Technique for Drawing Directed Graphs', IEEE Trans. on Software Engineering19(3), 214--230.]]

Digital Library

[12]

Gansner, E. R. & North, S. C. (1998), Improved Force-Directed Layouts, in S. H. Whitesides, ed., 'Proc. of the 6th Intl. Symp. on Graph Drawing (GD'98)', Vol. 1547 of LNCS, Springer-Verlag, pp. 364--373.]]

Digital Library

[13]

Himsolt, M. (2000), 'Graphlet: Design and Implementation of a Graph Editor', Software - Practice and Experience30(11), 1303--1324.]]

Digital Library

[14]

Koutsofios, E. & North, S. C. (1993), Drawing Graphs with Dot, Technical report, AT&T Bell Laboratories, Murray Hill NJ.]]

[15]

Messinger, E. B., Rowe, L. A. & Henry, R. R. (1991), 'A Divide-and-Conquer Algorithm for the Automatic Layout of Large Directed Graphs', IEEE Trans. on Systems, Man, and Cybernetics21(1), 1--11.]]

[16]

Misue, K., Eades, P., Lai, W. & Sugiyama, K. (1995), 'Layout Adjustment and the Mental Map', Journal of Visual Languages and Computing6, 183--210.]]

[17]

North, S. & Woodhull, G. (2002), Online Hierarchical Graph Drawing, in P. Mutzel et al., eds., 'Proc. of the 9th Intl. Symp. on Graph Drawing (GD 2001)', Vol. 2265 of LNCS, Springer-Verlag, pp. 232--246.]]

Digital Library

[18]

Rowe, L. A., Davis, M., Messinger, E., Meyer, C., Spirakis, C. & Tuan, A. (1987), 'A Browser for Directed Graphs', Software - Practice and Experience17(1), 61--76.]]

Digital Library

[19]

Sander, G. (1999), 'Graph Layout for Applications in Compiler Construction', Theoretical Computer Science217(2), 175--214.]]

Digital Library

[20]

Sugiyama, K., Tagawa, S. & Toda, M. (1981), 'Methods for Visual Understanding of Hierarchical System Structures', IEEE Trans. on Systems, Man, and CyberneticsSMC-11(2), 109--125.]]

[21]

Tamassia, R. (1987), 'On Embedding a Graph in the Grid with the Minimum Number of Bends', SIAM Journal on Computing16(3), 421--444.]]

Digital Library

Cited By

Dabaghian YCohn AFrank LSamet HShahabi CSchneider M(2007)Topological maps from signalsProceedings of the 15th annual ACM international symposium on Advances in geographic information systems10.1145/1341012.1341085(1-4)Online publication date: 7-Nov-2007
https://dl.acm.org/doi/10.1145/1341012.1341085
Blochinger WKaufmann MSiebenhaller M(2006)Visualization aided performance tuning of irregular task-parallel computationsInformation Visualization10.1057/palgrave.ivs.95001235:2(81-94)Online publication date: 1-Jun-2006
https://dl.acm.org/doi/10.1057/palgrave.ivs.9500123

Index Terms

Flexible layering in hierarchical drawings with nodes of arbitrary size

Recommendations

Convex drawings of hierarchical planar graphs and clustered planar graphs

In this paper, we present results on convex drawings of hierarchical graphs and clustered graphs. A convex drawing is a planar straight-line drawing of a plane graph, where every facial cycle is drawn as a convex polygon. Hierarchical graphs and ...
Small Drawings of Outerplanar Graphs, Series-Parallel Graphs, and Other Planar Graphs

In this paper, we study small planar drawings of planar graphs. For arbitrary planar graphs, ź(n2) is the established upper and lower bound on the worst-case area. A long-standing open problem is to determine for what graphs a smaller area can be ...
Compact drawings of 1-planar graphs with right-angle crossings and few bends
Abstract
We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is 1-planar if every ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image DL Hosted proceedings

ACSC '04: Proceedings of the 27th Australasian conference on Computer science - Volume 26

January 2004

367 pages

Editor:
Estivill-Castro

Publisher

Australian Computer Society, Inc.

Australia

Publication History

Published: 01 January 2004

Author Tags

Qualifiers

Article

Conference

ACSC '04

ACSC '04: Computer science

01 01 2004

Dunedin, New Zealand

Acceptance Rates

Overall Acceptance Rate 136 of 379 submissions, 36%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
364
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)11

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dabaghian YCohn AFrank LSamet HShahabi CSchneider M(2007)Topological maps from signalsProceedings of the 15th annual ACM international symposium on Advances in geographic information systems10.1145/1341012.1341085(1-4)Online publication date: 7-Nov-2007
https://dl.acm.org/doi/10.1145/1341012.1341085
Blochinger WKaufmann MSiebenhaller M(2006)Visualization aided performance tuning of irregular task-parallel computationsInformation Visualization10.1057/palgrave.ivs.95001235:2(81-94)Online publication date: 1-Jun-2006
https://dl.acm.org/doi/10.1057/palgrave.ivs.9500123

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents