|
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
|
|
|
|
[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.
|
