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

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
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
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. ...
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

54
Total Citations
View Citations
834
Total Downloads

Downloads (Last 12 months)128
Downloads (Last 6 weeks)17

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

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
Lee CChoi KShandler RKayser C(2021)Mapping Global Cyberterror Networks: An Empirical Study of Al-Qaeda and ISIS Cyberterrorism EventsJournal of Contemporary Criminal Justice10.1177/1043986221100160637:3(333-355)Online publication date: 15-Apr-2021
https://doi.org/10.1177/10439862211001606
Zhao ZZhang YFeng ZLewin-Eytan LCarmel DYom-Tov EAgichtein EGabrilovich E(2021)Towards Scalable Spectral Embedding and Data Visualization via Spectral CoarseningProceedings of the 14th ACM International Conference on Web Search and Data Mining10.1145/3437963.3441767(869-877)Online publication date: 8-Mar-2021
https://dl.acm.org/doi/10.1145/3437963.3441767
Gençer M(2020)Network VisualizationApplied Social Network Analysis With R10.4018/978-1-7998-1912-7.ch011(195-212)Online publication date: 2020
https://doi.org/10.4018/978-1-7998-1912-7.ch011
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