nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

The Bundled Crossing Number

verfasst von : Md. Jawaherul Alam, Martin Fink, Sergey Pupyrev

Erschienen in: Graph Drawing and Network Visualization

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We study the algorithmic aspect of edge bundling. A bundled crossing in a drawing of a graph is a group of crossings between two sets of parallel edges. The bundled crossing number is the minimum number of bundled crossings that group all crossings in a drawing of the graph.

We show that the bundled crossing number is closely related to the orientable genus of the graph. If multiple crossings and self-intersections of edges are allowed, the two values are identical; otherwise, the bundled crossing number can be higher than the genus.

We then investigate the problem of minimizing the number of bundled crossings. For circular graph layouts with a fixed order of vertices, we present a constant-factor approximation algorithm. When the circular order is not prescribed, we get a \(\frac{6c}{c-2}\)-approximation for a graph with n vertices having at least cn edges for \(c>2\). For general graph layouts, we develop an algorithm with an approximation factor of \(\frac{6c}{c-3}\) for graphs with at least cn edges for \(c > 3\).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Block Crossings in Storyline Visualizations

Nächstes Kapitel Approximating the Rectilinear Crossing Number

We thank an anonymous reviewer for suggesting this simplified proof.

Ackerman, E., Pinchasi, R.: On the degenerate crossing number. Discret. Comput. Geom. 49(3), 695–702 (2013)MathSciNetCrossRefMATH

Ajtai, M., Chvátal, V., Newborn, M.M., Szemerédi, E.: Crossing-free subgraphs. N.-Holl. Math. Stud. 60, 9–12 (1982)MathSciNetCrossRefMATH

Alam, M.J., Fink, M., Pupyrev, S.: The bundled crossing number. CoRR, cs.CG/1608.08161 (2016)

Baur, M., Brandes, U.: Crossing reduction in circular layouts. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 332–343. Springer, Heidelberg (2004). doi:10.1007/978-3-540-30559-0_28 CrossRef

Bouts, Q.W., Speckmann, B.: Clustered edge routing. In: PacificVis 2015, pp. 55–62 (2015)

Buchheim, C., Chimani, M., Gutwenger, C., Jünger, M., Mutzel, P.: Crossings and planarization. In: Handbook of Graph Drawing and Visualization. CRC Press (2013)

Cabello, S.: Hardness of approximation for crossing number. Discret. Comput. Geom. 49(2), 348–358 (2013)MathSciNetCrossRefMATH

Chuzhoy, J.: An algorithm for the graph crossing number problem. In: STOC 2011, pp. 303–312 (2011)

Cui, W., Zhou, H., Qu, H., Wong, P.C., Li, X.: Geometry-based edge clustering for graph visualization. TVCG 14(6), 1277–1284 (2008)

10.

Fraysseix, H., Mendez, P.O.: Stretching of Jordan arc contact systems. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 71–85. Springer, Heidelberg (2004). doi:10.1007/978-3-540-24595-7_7 CrossRef

11.

Dickerson, M., Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent drawings: visualizing non-planar diagrams in a planar way. JGAA 9(1), 31–52 (2005)MathSciNetCrossRefMATH

12.

Eppstein, D., Holten, D., Löffler, M., Nöllenburg, M., Speckmann, B., Verbeek, K.: Strict confluent drawing. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 352–363. Springer, Heidelberg (2013). doi:10.1007/978-3-319-03841-4_31 CrossRef

13.

Ersoy, O., Hurter, C., Paulovich, F.V., Cantareiro, G., Telea, A.: Skeleton-based edge bundling for graph visualization. TVCG 17(12), 2364–2373 (2011)

14.

Felsner, S., Valtr, P.: Coding and counting arrangements of pseudolines. Discret. Comput. Geom. 46(3), 405–416 (2011)MathSciNetCrossRefMATH

15.

Fink, M., Hershberger, J., Suri, S., Verbeek, K.: Bundled crossings in embedded graphs. In: Kranakis, E., Navarro, G., Chávez, E. (eds.) LATIN 2016. LNCS, vol. 9644, pp. 454–468. Springer, Heidelberg (2016). doi:10.1007/978-3-662-49529-2_34 CrossRef

16.

Fink, M., Pupyrev, S., Wolff, A.: Ordering metro lines by block crossings. JGAA 19(1), 111–153 (2015)MathSciNetCrossRefMATH

17.

Gansner, E. Hu, Y., North, S., Scheidegger, C.: Multilevel agglomerative edge bundling for visualizing large graphs. In: PacificVis 2011, pp. 187–194. IEEE (2011)

18.

Gansner, E.R., Koren, Y.: Improved circular layouts. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 386–398. Springer, Heidelberg (2007). doi:10.1007/978-3-540-70904-6_37 CrossRef

19.

Giordano, F., Liotta, G., Mchedlidze, T., Symvonis, A., Whitesides, S.: Computing upward topological book embeddings of upward planar digraphs. J. Discret. Algorithms 30, 45–69 (2015)MathSciNetCrossRefMATH

20.

Holten, D.: Hierarchical edge bundles: visualization of adjacency relations in hierarchical data. TVCG 12(5), 741–748 (2006)

21.

Holten, D., van Wijk, J.J.: Force-directed edge bundling for graph visualization. Comput. Graph. Forum 28(3), 983–990 (2009)CrossRef

22.

Lambert, A., Bourqui, R., Auber, D.: Winding roads: routing edges into bundles. Comput. Graph. Forum 29(3), 853–862 (2010)CrossRef

23.

Lazarus, F., Pocchiola, M., Vegter, G., Verroust, A.: Computing a canonical polygonal schema of an orientable triangulated surface. In: SoCG 2001, pp. 80–89. ACM (2001)

24.

Mohar, B.: The genus crossing number. ARS Math. Contempo. 2(2), 157–162 (2009)MathSciNetMATH

25.

Pach, J., Tóth, G.: Degenerate crossing numbers. Discret. Comput. Geom. 41(3), 376–384 (2009)MathSciNetCrossRefMATH

26.

Pupyrev, S., Nachmanson, L., Bereg, S., Holroyd, A.E.: Edge routing with ordered bundles. Comput. Geom. 52, 18–33 (2016)MathSciNetCrossRefMATH

27.

Schaefer, M.: The graph crossing number and its variants: a survey. Electron. J. Comb. Dyn. Surv. 21 (2013)

28.

Schaefer, M., Štefankovič, D.: The degenerate crossing number and higher-genus embeddings. In: Di Giacomo, E., Lubiw, A. (eds.) GD 2015. LNCS, vol. 9411, pp. 63–74. Springer, Heidelberg (2015). doi:10.1007/978-3-319-27261-0_6 CrossRef

29.

Shahrokhi, F., Sýkora, O., Székely, L.A., Vrt’o, I.: Book embeddings and crossing numbers. In: Mayr, E.W., Schmidt, G., Tinhofer, G. (eds.) WG 1994. LNCS, vol. 903, pp. 256–268. Springer, Heidelberg (1995). doi:10.1007/3-540-59071-4_53 CrossRef

30.

Thomassen, C.: The graph genus problem is NP-complete. J. Algorithms 10(4), 568–576 (1989)MathSciNetCrossRefMATH

31.

Yamanaka, K., Nakano, S., Matsui, Y., Uehara, R., Nakada, K.: Efficient enumeration of all ladder lotteries and its application. Theor. Comput. Sci. 411(16–18), 1714–1722 (2010)MathSciNetCrossRefMATH

Titel: The Bundled Crossing Number
verfasst von: Md. Jawaherul Alam
Martin Fink
Sergey Pupyrev
Verlag: Springer International Publishing
Buch: Graph Drawing and Network Visualization
Print ISBN: 978-3-319-50105-5

Electronic ISBN: 978-3-319-50106-2

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-50106-2_31

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"