Article

Free access

A fast multi-scale method for drawing large graphs

Authors:

David Harel,

Yehuda KorenAuthors Info & Claims

AVI '00: Proceedings of the working conference on Advanced visual interfaces

Pages 282 - 285

https://doi.org/10.1145/345513.345353

Published: 01 May 2000 Publication History

PDF eReader

Abstract

We present a multi-scale layout algorithm for the aesthetic drawing of undirected graphs with straight-line edges. The algorithm is extremely fast, and is capable of drawing graphs of substantially larger size than any other algorithm we are awars of. For example, the algorithm achieves optimal drawings of 1000 vertex graphs in less than 3 seconds. The paper contains graphs with over 6000 nodes. The proposed algorithm embodies a new multi-scale scheme for drawing graphs, which can significantly improve the speed of essentially any force-directed method.

Graphs have become an important part of recently proposed user interfaces, hence the relevance of this paper to work on interface issues.

References

[1]

G. D. Battista, P. Eades, R. Tamassia, and I. Tollis. Algorithms for the Visualization of Graphs. Prentice-Hall, 1999.]]

Digital Library

Google Scholar

[2]

R. Davidson and D. Hard. Drawing graphs nicely using simulated annealing. A CM Trans. on Graphics, 15:301-331, 1996.]]

Digital Library

Google Scholar

[3]

P. Eades. A heuristic for graph drawing. Congressus Numerantium, 42:149-160, 1984.]]

Google Scholar

[4]

D. S. H. (ed.). Approximation Algorithms for gP-Hard Problems. PWS Publishing Company, 1996.]]

Google Scholar

[5]

T. Fruchterman and E. Reingold. Graph drawing by force-directed placement. Software-Practice and Experience, 21:1129-1164, 1991.]]

Digital Library

Google Scholar

[6]

R. Hadany and D. Harel. A multi-scale method for drawing graphs nicely. In Proc. 25th Inter. Workshop on Graph-Theoretic Concepts in Computer Science, 1999.]]

Digital Library

Google Scholar

[7]

T. Kamada and S. Kawai. An algorithm for drawing general undirected graphs. Information Processing Letters, 31(5):7-15, 1989.]]

Digital Library

Google Scholar

Cited By

View all

Vasist PKrishnan SAgnihotri P(2025)The unfolding of geopolitical tensions on social networks: a social network analysis of Twitter and Reddit conversationsInternet Research10.1108/INTR-02-2024-0155Online publication date: 21-Jan-2025
https://doi.org/10.1108/INTR-02-2024-0155
Vasist PKrishnan SAzad NMekoth N(2025)A Comparison of ‘Organizing Forces’ on Reddit and YouTube Networks: Insights From the France Riots of 2023Information Systems Frontiers10.1007/s10796-025-10587-1Online publication date: 1-Mar-2025
https://doi.org/10.1007/s10796-025-10587-1
Ueno YNatsukawa HKoyamada K(2024)Do boxes affect exploration behavior and performance in group-in-a-box layouts?Journal of Visualization10.1007/s12650-024-01037-2Online publication date: 30-Dec-2024
https://doi.org/10.1007/s12650-024-01037-2
Show More Cited By

Index Terms

A fast multi-scale method for drawing large graphs

Recommendations

A Fast Multi-scale Method for Drawing Large Graphs
GD '00: Proceedings of the 8th International Symposium on Graph Drawing

We present a multi-scale layout algorithm for the aesthetic drawing of undirected graphs with straight-line edges. The algorithm is extremely fast, and is capable of drawing graphs of substantially larger size than any other algorithm we are aware of. ...
A Fast Multi-Scale Method for Drawing Large Graphs
Large Induced Forests in Graphs

In this article, we prove three theorems. The first is that every connected graph of order n and size m has an induced forest of order at least 8n-2m-2/9 with equality if and only if such a graph is obtained from a tree by expanding every vertex to a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

AVI '00: Proceedings of the working conference on Advanced visual interfaces

May 2000

317 pages

ISBN:1581132522

DOI:10.1145/345513

Chairmen:
Stefano Levialdi
Univ. di Roma “La Sapienza”, Roma, Italy
,
Vita Di Gesù
Univ. di Patermo, Patermo, Italy
,
Laura Tarantino
Univ. degli Studi dell'Aquila, L'Aquila, Italy

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 2000

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

AVI00

Sponsor:

SIGMM
SIGCHI
University of L'Aquila

AVI00: Advanced Visual Interfaces

Palermo, Italy

Acceptance Rates

Overall Acceptance Rate 128 of 490 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

57
Total Citations
View Citations
864
Total Downloads

Downloads (Last 12 months)127
Downloads (Last 6 weeks)15

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Vasist PKrishnan SAgnihotri P(2025)The unfolding of geopolitical tensions on social networks: a social network analysis of Twitter and Reddit conversationsInternet Research10.1108/INTR-02-2024-0155Online publication date: 21-Jan-2025
https://doi.org/10.1108/INTR-02-2024-0155
Vasist PKrishnan SAzad NMekoth N(2025)A Comparison of ‘Organizing Forces’ on Reddit and YouTube Networks: Insights From the France Riots of 2023Information Systems Frontiers10.1007/s10796-025-10587-1Online publication date: 1-Mar-2025
https://doi.org/10.1007/s10796-025-10587-1
Ueno YNatsukawa HKoyamada K(2024)Do boxes affect exploration behavior and performance in group-in-a-box layouts?Journal of Visualization10.1007/s12650-024-01037-2Online publication date: 30-Dec-2024
https://doi.org/10.1007/s12650-024-01037-2
Qu SYuan GXu HZhang YTang MZhu M(2023)Community detection: Concepts, algorithms, evaluation and challengesInternational Journal of Wavelets, Multiresolution and Information Processing10.1142/S021969132350053422:03Online publication date: 15-Nov-2023
https://doi.org/10.1142/S0219691323500534
Lyu YHuang XZhang Z(2023)Revisiting 2D Convolutional Neural Networks for Graph-Based ApplicationsIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2021.308361445:6(6909-6922)Online publication date: 1-Jun-2023
https://doi.org/10.1109/TPAMI.2021.3083614
Hocevar K(2023)Who Drives Disaster Communication? An Analysis of Twitter Network Structure and Influence during a Wildfire CrisisWestern Journal of Communication10.1080/10570314.2023.216905288:4(840-860)Online publication date: 24-Jan-2023
https://doi.org/10.1080/10570314.2023.2169052
Koulocheri EXenos M(2022)Correlating Formal Assessment with Social Network Activity within a Personal Learning EnvironmentResearch Anthology on Applying Social Networking Strategies to Classrooms and Libraries10.4018/978-1-6684-7123-4.ch019(340-354)Online publication date: 8-Jul-2022
https://doi.org/10.4018/978-1-6684-7123-4.ch019
Xu ZMao TXu GWang YLin D(2022)Multivariate Network Layout Using Force-Directed Method with Attribute ConstraintsApplied Sciences10.3390/app1209456112:9(4561)Online publication date: 30-Apr-2022
https://doi.org/10.3390/app12094561
Binkheder SAldekhyyel RAlMogbel AAl-Twairesh NAlhumaid NAldekhyyel SJamal A(2021)Public Perceptions around mHealth Applications during COVID-19 Pandemic: A Network and Sentiment Analysis of Tweets in Saudi ArabiaInternational Journal of Environmental Research and Public Health10.3390/ijerph18241338818:24(13388)Online publication date: 20-Dec-2021
https://doi.org/10.3390/ijerph182413388
Pérez Dasilva JMeso Ayerdi KMendiguren Galdospin T(2021)Deepfakes on Twitter: Which Actors Control Their Spread?Media and Communication10.17645/mac.v9i1.34339:1(301-312)Online publication date: 3-Mar-2021
https://doi.org/10.17645/mac.v9i1.3433
Show More Cited By

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.

Cited By

Index Terms

Recommendations

A Fast Multi-scale Method for Drawing Large Graphs

A Fast Multi-Scale Method for Drawing Large Graphs

Large Induced Forests in Graphs