Article

Free access

Using spring algorithms to remove node overlapping

Authors:

Wanchun Li,

Peter Eades,

Nikola NikolovAuthors Info & Claims

APVis '05: proceedings of the 2005 Asia-Pacific symposium on Information visualisation - Volume 45

Pages 131 - 140

Published: 01 January 2005 Publication History

PDF eReader

Abstract

Cluttered drawings of graphs cannot effectively convey the information of graphs. Two issues might cause node overlapping when one draws a picture of a graph. The first issue occurs when applying a layout algorithm for an abstract graph to a practical application in which nodes are labeled. The second is the changing of a node's size in a dynamic drawing system. This paper presents two algorithms, DNLS and ODNLS, for removing the two kinds of overlapping. The algorithms are based on the well-known spring embedder model. The outputs of the algorithms provide the features of spring algorithms. Experiments are carried out to compare DNLS and ODNLS to the Force Scan(FS) algorithm and its variants. The results demonstrate the advantages of DNLS and ODNLS in terms of some aesthetic criteria.

References

[1]

Gansner E. & North S. (1998), Improved Force-Directed Layouts, in 'Graph Drawing', LNCS, Montreal, Canada, August 13--15, pp. 364--373.

Digital Library

Google Scholar

[2]

Hayashi K., Inoue M., Masuzawa T., & Fujiwara H. (1998), A layout Adjustment Problem fo Disjoint Rectangles Preserving Orthogonal Order, in 'Graph Drawing', LNCS, Montreal, Canada, August 13--15, pp. 183--197.

Digital Library

Google Scholar

[3]

Huang X., & Lai W. (2003), Force-Transfer: A New Approach to Removing Overlapping Nodes in Graph Layout, in '25th Australian Computer Science Conference', Adelaida, Australia, 2003.

Digital Library

Google Scholar

[4]

Kamps T., Kleinz J., & Read J. (1995), Constraint-Based Spring-Model Algorithm for Graph Layout, in 'Graph Drawing', LNCS, F. J. Brandenburg, Canada, 1996, pp. 349--360.

Digital Library

Google Scholar

[5]

Generating customized layouts. in 'Graph Drawing', LNCS, F. J. Brandenburg, Canada, 1996, pp. 504--515.

Digital Library

Google Scholar

[6]

Di Battista G., Eades P., Tamassia R.,& Tollis I., (1998), Graph drawing: algorithms for the visualization of graphs, Prentice Hall.

Digital Library

Google Scholar

[7]

Eades P. (1984), 'A Heuristci Graph Drawing', Congressus Numerantium42,1984.

Google Scholar

[8]

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

Google Scholar

[9]

Eades P., & Lin X. (1999), 'Spring Algorithms and Symmetry', Theoretical Computer Science240-2, 379--405, 2000.

Digital Library

Google Scholar

[10]

Harel D. &Koren Y. (1999), 'Drawing Graphs with Non-Uniform Vertices', in 'Proceedings of Working Conference on Advanced Visual Interfaces (AVI'02), Italy, 2002, pp. 157--166.

Digital Library

Google Scholar

[11]

Lyons K., Meijer H.,& Rappaport D., (1998), 'Algorithms for Cluter Busting in Anchored Graph Drawing', J. Graph Algorithms and Applications2-1, 1--24, 1998.

Google Scholar

[12]

Marriott K., Stuckey P., Tam V., & He W. (1995), 'Removing Node Overlapping in Graph Layout Using Constrained Optimization', Constraints8, 143--171, 2003.

Digital Library

Google Scholar

Cited By

View all

van Garderen MPampel BNocaj ABrandes U(2017)Minimum-Displacement Overlap Removal for Geo-referenced Data VisualizationComputer Graphics Forum10.1111/cgf.1319936:3(423-433)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1111/cgf.13199
Rüegg ULakkundi RPrasad AKodaganur ASchulze Cvon Hanxleden RBaudry BCombemale BKienzle JPretschner A(2016)Incremental diagram layout for automated model migrationProceedings of the ACM/IEEE 19th International Conference on Model Driven Engineering Languages and Systems10.1145/2976767.2976805(185-195)Online publication date: 2-Oct-2016
https://dl.acm.org/doi/10.1145/2976767.2976805
Klapaukh RPearce DMarshall S(2015)Comparing Graph Layouts for Vertex Selection TasksProceedings of the Annual Meeting of the Australian Special Interest Group for Computer Human Interaction10.1145/2838739.2838740(557-565)Online publication date: 7-Dec-2015
https://dl.acm.org/doi/10.1145/2838739.2838740
Show More Cited By

Index Terms

Using spring algorithms to remove node overlapping

Recommendations

Node overlap removal in clustered directed acyclic graphs

Graph drawing and visualization represent structural information as diagrams of abstract graphs and networks. An important subset of graphs is directed acyclic graphs (DAGs). This paper presents a new E-Spring algorithm, extended from the popular spring ...
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

APVis '05: proceedings of the 2005 Asia-Pacific symposium on Information visualisation - Volume 45

January 2005

146 pages

ISBN:1920682279

Editor:
Seok-Hee Hong
NICTA, Australia

Publisher

Australian Computer Society, Inc.

Australia

Publication History

Published: 01 January 2005

Author Tags

Qualifiers

Article

Conference

APVis '05

APVis '05: Information visualisation

01 01 2005

Sydney, Australia

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
666
Total Downloads

Downloads (Last 12 months)84
Downloads (Last 6 weeks)10

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

van Garderen MPampel BNocaj ABrandes U(2017)Minimum-Displacement Overlap Removal for Geo-referenced Data VisualizationComputer Graphics Forum10.1111/cgf.1319936:3(423-433)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1111/cgf.13199
Rüegg ULakkundi RPrasad AKodaganur ASchulze Cvon Hanxleden RBaudry BCombemale BKienzle JPretschner A(2016)Incremental diagram layout for automated model migrationProceedings of the ACM/IEEE 19th International Conference on Model Driven Engineering Languages and Systems10.1145/2976767.2976805(185-195)Online publication date: 2-Oct-2016
https://dl.acm.org/doi/10.1145/2976767.2976805
Klapaukh RPearce DMarshall S(2015)Comparing Graph Layouts for Vertex Selection TasksProceedings of the Annual Meeting of the Australian Special Interest Group for Computer Human Interaction10.1145/2838739.2838740(557-565)Online publication date: 7-Dec-2015
https://dl.acm.org/doi/10.1145/2838739.2838740
Klapaukh RPearce DMarshall S(2014)Towards a vertex and edge label aware force directed layout algorithmProceedings of the Thirty-Seventh Australasian Computer Science Conference - Volume 14710.5555/2667473.2667477(29-37)Online publication date: 20-Jan-2014
https://dl.acm.org/doi/10.5555/2667473.2667477
Ukrop JČíková ZKapec PO'Sullivan C(2013)Visual access to graph content using magic lenses and filteringProceedings of the 28th Spring Conference on Computer Graphics10.1145/2448531.2448534(23-30)Online publication date: 10-Mar-2013
https://dl.acm.org/doi/10.1145/2448531.2448534
Tu Y(2010)Multi-conProceedings of the International Conference on Advanced Visual Interfaces10.1145/1842993.1843039(259-266)Online publication date: 26-May-2010
https://dl.acm.org/doi/10.1145/1842993.1843039
Kumar PZhang KShin SOssowski S(2009)Visualization of clustered directed acyclic graphs with node interleavingProceedings of the 2009 ACM symposium on Applied Computing10.1145/1529282.1529685(1800-1805)Online publication date: 8-Mar-2009
https://dl.acm.org/doi/10.1145/1529282.1529685
Kumar PZhang K(2009)Node overlap removal in clustered directed acyclic graphsJournal of Visual Languages and Computing10.1016/j.jvlc.2009.04.00720:6(403-419)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1016/j.jvlc.2009.04.007

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Abstract

References

Cited By

Index Terms

Recommendations

Node overlap removal in clustered directed acyclic graphs

Small Drawings of Outerplanar Graphs, Series-Parallel Graphs, and Other Planar Graphs

Compact drawings of 1-planar graphs with right-angle crossings and few bends

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Conference

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations