A Note on the Self-similarity of Some Orthogonal Drawings

Patrignani, Maurizio (2004) A Note on the Self-similarity of Some Orthogonal Drawings. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 389-394 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_39).

Full text not available from this repository.

Abstract

Large graphs are difficult to browse and to visually explore. This note adds up evidence that some graph drawing techniques, which produce readable layouts when applied to medium-size graphs, yield self-similar patterns when launched on huge graphs. To prove this, we consider the problem of assessing the self-similarity of graph drawings, and measure the box-counting dimension of the output of three algorithms, each using a different approach for producing orthogonal grid drawings with a reduced number of bends. Work partially supported by European Commission – Fet Open project COSIN – COevolution and Self-organisation In dynamical Networks – IST-2001-33555, by European Commission – Fet Open project DELIS – Dynamically Evolving Large Scale Information Systems – Contract no 001907, by ldquoProgetto ALINWEB: Algoritmica per Internet e per il Webrdquo, MIUR Programmi di Ricerca Scientifica di Rilevante Interesse Nazionale, and by ldquoThe Multichannel Adaptive Information Systems (MAIS) Projectrdquo, MIUR Fondo per gli Investimenti della Ricerca di Base.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_39
Classifications:Z Theory > Z.999 Others
P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:609

Repository Staff Only: item control page

References

J. Boyer and W. Myrvold. Stop minding your P's and Q's: A simplified 0(n) planar embedding algorithm. In 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 140-146, 1999.

H. de Fraysseix and P. Ossona de Mendez. P.I.G.A.L.E. - Public Implementation of a Graph Algorithm Library and Editor. SourceForge project page http://sourceforge.net/projects/pigale

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

K. Falconer. Fractal Geometry: Mathematical Foundations and Applications. John Wiley & Sons Ltd, second edition, 2003.

U. Fößmeier and M. Kaufmann. Drawing high degree graphs with low bend numbers. In F. J. Brandenburg, editor, Graph Drawing (Proc. GD '95), volume 1027 of Lecture Notes in Comput. Sci., pages 254-266. Springer-Verlag, 1996.

B. B. Mandelbrot. The Fractal Geometry of Nature. W. H. Freeman and Company, New York, 1977.

A. Papacostas and I. Tollis. Efficient orthogonal drawings of high degree graphs. Algorithmica, 26:100-125, 2000.

M. Schroeder. Fractals, chaos, power laws: minutes from an infinite paradise. W. H. Freeman and Company, New York, 1991.

G. Siganos, M. Faloutsos, P. Faloutsos and C. Faloutsos. Power laws and the as-level internet topology. In IEEE/ACM Transactions on Networking (TON), volume 11, pages 514-524. ACM Press, 2003.

R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput., 16(3):421-444, 1987.

L. Wu and C. Faloutsos. FracDim, jan 2001. Perl package available at http://www.andrew.cmu.edu/~lw2j/downloads. html

S.-H. Yook, H. Jeong, and A.-L. Barabasi. Modeling the Internet's large scale topology. In Proc. PNAS'02, 2002.