A 9-spoked wheel and its line graph.

[Graphics:Images/speed_gr_1.gif]
[Graphics:Images/speed_gr_2.gif]
[Graphics:Images/speed_gr_3.gif]

[Graphics:Images/speed_gr_4.gif]

[Graphics:Images/speed_gr_5.gif]

The following creates a sequence of 10 semirandom 4-regular graphs of orders 20, 40,  60,..., 200. The line graph of each generated 4-regular graph is constructed and the time to construct the line graph is recorded.

[Graphics:Images/speed_gr_6.gif]
[Graphics:Images/speed_gr_7.gif]

In the following, the same experiment is done with the "old" Combinatorica functions.

[Graphics:Images/speed_gr_8.gif]
[Graphics:Images/speed_gr_9.gif]

"Old" Combinatorica builds the line graph of a 4-regular 200-vertex  in 14.19 seconds. The new implementation takes a mere 0.59 seconds! More important is what is revealed by the plots of the running times shown below.  The new Combinatorica plot is linear while the old Combinatorica plot seems to indicate quadratic running time.

[Graphics:Images/speed_gr_10.gif]

[Graphics:Images/speed_gr_11.gif]

[Graphics:Images/speed_gr_12.gif]


Converted by Mathematica      September 9, 2000