Abstract
We propose a layout algorithm for micro/macro graphs, i.e. relational structures with two levels of detail. While the micro-level graph is given, the macro-level graph is induced by a given partition of the micro-level vertices. A typical example is a social network of employees organized into different departments. We do not impose restrictions on the macro-level layout other than sufficient thickness of edges and vertices, so that the micro-level graph can be placed on top of the macro-level graph. For the micro-level graph we define a combinatorial multi-circular embedding and present corresponding layout algorithms based on edge crossing reduction strategies.
Research partially supported by DFG, grants Wa 654/13-2 and Br 2158/2-3.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Archambault, D., Munzner, T., Auber, D.: Topolayout: Multi-level graph layout by topological features. IEEE Trans. Visual. and Comp. Graphics 13(2), 305–317 (2007)
Bachmaier, C.: A radial adaptation of the sugiyama framework for visualizing hierarchical information. IEEE Trans. Visual. and Comp. Graphics 13(3), 585–594 (2007)
Balzer, M., Deussen, O.: Level-of-detail visualization of clustered graph layouts. In: APVIS 2007. Asia-Pacific Symposium on Visualisation 2007 (2007)
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)
Brandes, U., Erlebach, T. (eds.): Network Analysis. LNCS, vol. 3418. Springer, Heidelberg (2005)
Cox, T.F., Cox, M.A.A.: Multidimensional Scaling. In: Monographs on Statistics and Applied Probability, 2nd edn., Chapman & Hall/CRC (2001)
Duncan, C.A., Efrat, A., Kobourov, S.G., Wenk, C.: Drawing with fat edges. In: Mutzel, P., Jünger, M., Leipert, S. (eds.) GD 2001. LNCS, vol. 2265, pp. 162–177. Springer, Heidelberg (2002)
Eades, P., Kelly, D.: Heuristics for reducing crossings in 2-layered networks. Ars Combinatoria 21(A), 89–98 (1986)
Fruchterman, T.M.J., Reingold, E.M.: Graph drawing by force-directed placement. Software - Practice and Experience 21(11), 1129–1164 (1991)
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)
Gansner, E.R., North, S.C.: Improved force-directed layouts. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 364–373. Springer, Heidelberg (1999)
Harel, D., Koren, Y.: Drawing graphs with non-uniform vertices. In: AVI 2002. Proc. Work. Conf. on Advanced Visual Interfaces, pp. 157–166. ACM Press, New York (2002)
Holten, D.: Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data. IEEE Trans. Visual. and Comp. Graphics 12(5), 741–748 (2006)
Kaufmann, M., Wiese, R.: Maintaining the mental map for circular drawings. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol. 2528, pp. 12–22. Springer, Heidelberg (2002)
Krebs, V.E.: Visualizing human networks. Release 1.0, pp. 1–25 (February 1996)
Krempel, L.: Visualisierung komplexer Strukturen. Grundlagen der Darstellung mehrdimensionaler Netzwerke. Campus (2005)
Masuda, S., Kashiwabara, T., Nakajima, K., Fujisawa, T.: On the \(\mathcal{NP}\)-completeness of a computer network layout problem. In: Proc. 20th IEEE Int. Symposium on Circuits and Systems 1987, pp. 292–295 (1987)
Matuszewski, C., Schönfeld, R., Molitor, P.: Using sifting for k-layer straightline crossing minimization. In: Kratochvíl, J. (ed.) GD 1999. LNCS, vol. 1731, pp. 217–224. Springer, Heidelberg (1999)
Rudell, R.: Dynamic variable ordering for ordered binary decision diagrams. In: Proc. IEEE/ACM Conf. Computer-Aided Design, pp. 42–47. IEEE Society, Los Alamitos (1993)
Six, J.M., Tollis, I.G.: A framework for user-grouped circular drawings. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 135–146. Springer, Heidelberg (2004)
Wang, X., Miyamoto, I.: Generating customized layouts. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 504–515. Springer, Heidelberg (1996)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Baur, M., Brandes, U. (2008). Multi-circular Layout of Micro/Macro Graphs. In: Hong, SH., Nishizeki, T., Quan, W. (eds) Graph Drawing. GD 2007. Lecture Notes in Computer Science, vol 4875. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77537-9_26
Download citation
DOI: https://doi.org/10.1007/978-3-540-77537-9_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77536-2
Online ISBN: 978-3-540-77537-9
eBook Packages: Computer ScienceComputer Science (R0)