Graph Gallery


Simple, planar, connected graph. Generated with P.I.G.A.L.E. library [2] by asking for a planar connected graph with 10,000 edges. When the graph was simplified 6,515 edges survided. The number of nodes is 4,970. The graph was planarized by using the Boyer and Myrvold algorithm [3]. The graph was orthogonalized by using the Tamassia algorithm [4] (and in particular the formulation of [9] for handling high degree graphs) in order to minimize the number of bends (which is 2,567 for this planar embedding). The compaction step was performed with a heuristic based on face rectangularization [4][7]. The bounding box (number of grid lines) is 1,295 x 1,356. The box-counting fractal dimension computed with the package [6] is 1.69. Self-similarity in orthogonal drawings is discussed in [1].
High resolution picture (1,244,258 Bytes)
Conn-P_10000_0.POO.FC.1.high.gif
Low resolution picture (336,920 Bytes)
Conn-P_10000_0.POO.FC.1.low.gif
Zooming of previous picture (148,657 Bytes)
Conn-P_10000_0.POO.FC.2.gif
Zooming of previous picture (148,657 Bytes)
Conn-P_10000_0.POO.FC.3.gif
Simple, planar, connected graph. Generated with P.I.G.A.L.E. library [2] by asking for a planar connected graph with 9,500 edges. The graph was simplified by removing multiple edges (6,155 survived simplification). The number of nodes is 4,700. The graph was planarized by using the Boyer and Myrvold algorithm [3]. The graph was orthogonalized by using the Tamassia algorithm [4] (and in particular the formulation of [9] for handling high degree graphs) in order to minimize the number of bends (which is 2,463 for this planar embedding). The compaction step was performed with a heuristic based on face rectangularization [4][7]. .
Picture of the whole graph (319,354 Bytes)
Conn-P_9500_5.1.gif
Zooming of previous picture (355,156 Bytes)
Conn-P_9500_5.2.gif
Zooming of previous picture (353,376 Bytes)
Conn-P_9500_5.3.gif
Zooming of previous picture (354,259 Bytes)
Conn-P_9500_5.4.gif
Zooming of previous picture (351,145 Bytes)
Conn-P_9500_5.5.gif
Simple, maximal planar (all faces have three edges). Generated with LEDA library [5]. The graph has 5,000 nodes and 14,994 (= 5,000 x 3 - 6) edges. The graph was planarized by using the Boyer and Myrvold algorithm [3]. The graph was orthogonalized by using the Tamassia algorithm [4] (and in particular the formulation of [9] for handling high degree graphs) in order to minimize the number of bends (which is 12,455 for this planar embedding). The compaction step was performed with a heuristic based on face rectangularization [4][7]. The bounding box (number of grid lines) is 1,512 x 1,414. The box-counting fractal dimension computed with the package [6] is 1.70. Self-similarity in orthogonal drawings is discussed in [1].
This drawing won an honorable mention in the 11th Annual Graph Drawing Competition.
GIF high resolution picture (1,528,343 Bytes)
MaxPlan-L_5000_0.POO.FC.1.high.gif
JPG high resolution picture (125,151 Bytes)
MaxPlan-L_5000_0.POO.FC.1.high.jpg
GIF low resolution picture (325,089 Bytes)
MaxPlan-L_5000_0.POO.FC.1.low.gif
JPG low resolution picture (66,303 Bytes)
MaxPlan-L_5000_0.POO.FC.1.low.jpg
Zooming of previous picture (91,751 Bytes)
MaxPlan-L_5000_0.POO.FC.2.gif
Zooming of previous picture (131,235 Bytes)
MaxPlan-L_5000_0.POO.FC.3.gif
Simple, planar, triconnected graph. Generated with P.I.G.A.L.E. library [2]. The graph was simplified by removing multiple edges (10,095 survived). The number of nodes is 5,046. The graph was planarized by using the Boyer and Myrvold algorithm [3]. The graph was orthogonalized by using the Tamassia algorithm [4] (and in particular the formulation of [9] for handling high degree graphs) in order to minimize the number of bends (which is 3,844 for this planar embedding). The compaction step was performed with a heuristic based on face rectangularization [4][7]. The bounding box (number of grid lines) is 1,027 x 1,273. The box-counting fractal dimension computed with the package [6] is 1.64. Self-similarity in orthogonal drawings is discussed in [1].
High resolution picture (933,076 Bytes)
Triconn-P_10000_0.POO.FC.1.high.gif
Low resolution picture (333,678 Bytes)
Triconn-P_10000_0.POO.FC.1.low.gif
Zooming of previous picture (148,657 Bytes)
Triconn-P_10000_0.POO.FC.2.gif
Zooming of previous picture (148,657 Bytes)
Triconn-P_10000_0.POO.FC.3.gif
Simple, planar, connected graph. Generated with P.I.G.A.L.E. library [2] by asking for a graph with 3,500 edges. The graph was simplified by removing multiple edges. The number of nodes is about 1,500. This orthogonal grid drawing was obtained starting from a visibility representation of the graph. The original formulation of this algorithm [7] only works for graphs of maximum degree four, but it was easily modified in order to handle high degree graphs and to produce drawings having at most two bends per edge.
Picture of the whole drawing (205,677 Bytes)
Biconn-P_3500_1.OFV.1.gif
Zooming of previous picture (99,658 Bytes)
Biconn-P_3500_1.OFV.2.gif
Zooming of previous picture (96,792 Bytes)
Biconn-P_3500_1.OFV.3.gif
Simple, planar, connected graph. Generated with P.I.G.A.L.E. library [2] by asking for a graph with 3,500 edges. The graph was simplified by removing multiple edges. The number of nodes is about 1,500. This orthogonal grid drawing was obtained with an approach based on the Relative Coordinate Scenario which consists of the incremental construction of the drawing. Additional rows and columns are inserted in order to allow the placement of new nodes and the routing of their incident edges. The "simple algorithm" described in [8] for drawing high degree biconnected graphs was used to produce this drawing. The drawing has intersections even if the original graph is planar, but each edge is guaranteed to have a single bend.
Picture of the whole drawing (306,362 Bytes)
Biconn-P_3500_1.RCS.1.gif
Zooming of previous picture (145,207 Bytes)
Biconn-P_3500_1.RCS.2.gif
Zooming of previous picture (110,836 Bytes)
Biconn-P_3500_1.RCS.3.gif

References


[1]

Maurizio Patrignani, "A Note on the Self-Similarity of Some Orthogonal Drawings", to appear in János Pach, editor, Graph Drawing (Proc. GD '04), Lecture Notes Comput. Sci., Springer-Verlag.

[2]

H. de Frayssex 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.

[3]

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

[4]

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

[5]

M. Mehlhorn and S. Naher, "LEDA: A Platform for Combinatorial and Geometric Computing", Cambridge University Press, New York, 1998.

[6]

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

[7]

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

[8]

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

[9]

U. Foessmeier 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 Comput. Sci., pages 254-266. Springer-Verlag, 1996.