Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cover of the book

2015 | OriginalPaper | Chapter

GraphMaps: Browsing Large Graphs as Interactive Maps

Authors : Lev Nachmanson, Roman Prutkin, Bongshin Lee, Nathalie Henry Riche, Alexander E. Holroyd, Xiaoji Chen

Published in: Graph Drawing and Network Visualization

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Algorithms for laying out large graphs have seen significant progress in the past decade. However, browsing large graphs remains a challenge. Rendering thousands of graphical elements at once often results in a cluttered image, and navigating these elements naively can cause disorientation. To address this challenge we propose a method called GraphMaps, mimicking the browsing experience of online geographic maps.
GraphMaps creates a sequence of layers, where each layer refines the previous one. During graph browsing, GraphMaps chooses the layer corresponding to the zoom level, and renders only those entities of the layer that intersect the current viewport. The result is that, regardless of the graph size, the number of entities rendered at each view does not exceed a predefined threshold, yet all graph elements can be explored by the standard zoom and pan operations.
GraphMaps preprocesses a graph in such a way that during browsing, the geometry of the entities is stable, and the viewer is responsive. Our case studies indicate that GraphMaps is useful in gaining an overview of a large graph, and also in exploring a graph on a finer level of detail.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
next chapter An Incremental Layout Method for Visualizing Online Dynamic Graphs
Footnotes
Literature
1.
Abello, J., van Ham, F., Krishnan, N.: Ask-graphview: a large scale graph visualization system. IEEE Trans. Vis. Comput. Graph. 12(5), 669–676 (2006)CrossRef
2.
Abello, J., Kobourov, S.G., Yusufov, R.: Visualizing large graphs with compound-fisheye views and treemaps. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 431–441. Springer, Heidelberg (2005) CrossRef
3.
Auber, D.: Using Strahler numbers for real time visual exploration of huge graphs. In: Computer Vision and Graphics (ICCVG’02), pp. 56–69 (2002)
4.
Auber, D.: Tulip - a huge graph visualization framework. In: Graph Drawing Software, pp. 105–126 (2004)
5.
Auber, D., Chiricota, Y., Jourdan, F., Melançon, G.: Multiscale visualization of small world networks. In: IEEE Symposium on Information Visualization (INFOVIS’03), pp. 75–81 (2003)
6.
Balzer, M., Deussen, O.: Level-of-detail visualization of clustered graph layouts. In: Asia-Pacific Symposium on Information Visualisation (APVIS’07), pp. 133–140. IEEE (2007)
7.
Bastian, M., Heymann, S., Jacomy, M.: Gephi: an open source software for exploring and manipulating networks. In: International AAAI Conference on Weblogs and Social Media (ICWSM’09) (2009)
8.
Brandes, U.: A faster algorithm for betweenness centrality. J. Math. Sociol. 25(2), 163–177 (2001)MATHCrossRef
9.
Brandes, U., Pich, C.: Eigensolver methods for progressive multidimensional scaling of large data. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 42–53. Springer, Heidelberg (2007) CrossRef
10.
Brunel, E., Gemsa, A., Krug, M., Rutter, I., Wagner, D.: Generalizing geometric graphs. In: Speckmann, B. (ed.) GD 2011. LNCS, vol. 7034, pp. 179–190. Springer, Heidelberg (2011) CrossRef
11.
Eades, P., Feng, Q.-W.: Multilevel visualization of clustered graphs. In: North, S.C. (ed.) GD 1996. LNCS, vol. 1190, pp. 101–112. Springer, Heidelberg (1997) CrossRef
12.
van den Elzen, S., van Wijk, J.: Multivariate network exploration and presentation: from detail to overview via selections and aggregations. IEEE Trans. Vis. Comput. Graph. 20(12), 2310–2319 (2014)CrossRef
13.
Gansner, E.R., Koren, Y., North, S.C.: Topological fisheye views for visualizing large graphs. IEEE Trans. Vis. Comput. Graph. 11(4), 457–468 (2005)CrossRef
14.
Gansner, E., Hu, Y., Kobourov, S.: Gmap: visualizing graphs and clusters as maps. In: IEEE Pacific Visualization Symposium (PacificVis’10), pp. 201–208. IEEE (2010)
15.
van Ham, F., van Wijk, J.: Interactive visualization of small world graphs. In: IEEE Symposium on Information Visualization (INFOVIS’04), pp. 199–206 (2004)
16.
van Ham, F., Perer, A.: Search, show context, expand on demand: supporting large graph exploration with degree-of-interest. IEEE Trans. Vis. Comput. Graph. 15(6), 953–960 (2009)CrossRef
17.
Henry, N., Bezerianos, A., Fekete, J.D.: Improving the readability of clustered social networks using node duplication. IEEE Trans. Vis. Comput. Graph. 14(6), 1317–1324 (2008)CrossRef
18.
Henry, N., Fekete, J.D., McGuffin, M.J.: NodeTrix: a hybrid visualization of social networks. IEEE Trans. Vis. Comput. Graph. 13(6), 1302–1309 (2007)CrossRef
19.
Nachmanson, L., Prutkin, R., Lee, B., Riche, N.H., Holroyd, A.E., Chen, X.: Graphmaps: Browsing large graphs as interactive maps. CoRR arXiv:​1506.​06745 (2015)
20.
Nocaj, A., Ortmann, M., Brandes, U.: Untangling hairballs. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 101–112. Springer, Heidelberg (2014)
21.
Page, L., Brin, S., Motwani, R., Winograd, T.: The PageRank citation ranking: Bringing order to the web. Technical report 1999–66, Stanford InfoLab (1999)
22.
Perer, A., Shneiderman, B.: Balancing systematic and flexible exploration of social networks. IEEE Trans. Vis. Comput. Graph. 12(5), 693–700 (2006)CrossRef
23.
Shewchuk, J.R.: Delaunay refinement algorithms for triangular mesh generation. Comput. Geom. Theory Appl. 22(1–3), 21–74 (2002)MATHMathSciNetCrossRef
24.
Traud, A.L., Kelsic, E.D., Mucha, P.J., Porter, M.A.: Comparing community structure to characteristics in online collegiate social networks. SIAM Rev. 53(3), 526–543 (2011)MathSciNetCrossRef
25.
Wu, H.-Y., Takahashi, S., Lin, C.-C., Yen, H.-C.: A zone-based approach for placing annotation labels on metro maps. In: Dickmann, L., Volkmann, G., Malaka, R., Boll, S., Krüger, A., Olivier, P. (eds.) SG 2011. LNCS, vol. 6815, pp. 91–102. Springer, Heidelberg (2011) CrossRef
26.
Zinsmaier, M., Brandes, U., Deussen, O., Strobelt, H.: Interactive level-of-detail rendering of large graphs. IEEE Trans. Vis. Comput. Graph. 18(12), 2486–2495 (2012)CrossRef
Metadata
Title
GraphMaps: Browsing Large Graphs as Interactive Maps
Authors
Lev Nachmanson
Roman Prutkin
Bongshin Lee
Nathalie Henry Riche
Alexander E. Holroyd
Xiaoji Chen
Copyright Year
2015
Book
Graph Drawing and Network Visualization

Print ISBN: 978-3-319-27260-3

Electronic ISBN: 978-3-319-27261-0

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-27261-0_1

Premium Partner

    Image Credits