Drawing Big Graphs Using Spectral Sparsification

DOI10.1007/978-3-319-73915-1_22MaRDI QIDQ4625115zbMATH OpenOpenAlexFDO

Authors

Publication date 20 February 2019

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.08659

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Spectral sparsification is a general technique developed by Spielman et al. to reduce the number of edges in a graph while retaining its structural properties. We investigate the use of spectral sparsification to produce good visual representations of big graphs. We evaluate spectral sparsification approaches on real-world and synthetic graphs. We show that spectral sparsifiers are more effective than random edge sampling. Our results lead to guidelines for using spectral sparsification in big graph visualization.

Recommendations

• Spectral sparsification of graphs
• On spectral graph drawing
• Drawing Huge Graphs by Algebraic Multigrid Optimization
• scientific article; zbMATH DE number 2080098
• A Fast Multi-Scale Method for Drawing Large Graphs
• Drawing large graphs by multilevel maxent-stress optimization
• scientific article; zbMATH DE number 1974121
• Graph Drawing by High-Dimensional Embedding
• A general framework for graph sparsification
• A general framework for graph sparsification

Cites work

• Generalized inverses. Theory and applications.
• Graph Drawing
• Handbook of Graph Theory
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 1256718 (Why is no real title available?)
• scientific article; zbMATH DE number 878897 (Why is no real title available?)
• scientific article; zbMATH DE number 5485569 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Shape-Based Quality Metrics for Large Graph Visualization
• Spectral sparsification of graphs
• The relative neighbourhood graph of a finite planar set
• The University of Florida sparse matrix collection

Cited in

(5)

• Shape simplification through graph sparsification
• Graph reduction with spectral and cut guarantees
• Visualizing Sparse Filtrations.
• Connectivity-faithful graph drawing
• Planar stories of graph drawings: algorithms and experiments

This page was built for publication: Drawing Big Graphs Using Spectral Sparsification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4625115)