Hello Vitaliy,

I'd just like to point out that this kind of measurement:

ti = AbsoluteTime[];

GraphPlot[EdgeRules[g]]

AbsoluteTime[] - ti

for plotting things is not reliable.

There are several stages to rendering a graphic on screen, and not all of them happen in the kernel. A better way to

*estimate* the times is this:

In[1]:= g = RandomGraph[{10000, 20000}, GraphLayout -> None]; // AbsoluteTiming

Out[1]= {0.007185, Null}

In[2]:= g = SetProperty[g, GraphLayout -> Automatic];

In[3]:= GraphEmbedding[g]; // AbsoluteTiming

Out[3]= {4.454666, Null}

In[4]:= boxes = ToBoxes[g]; // AbsoluteTiming

Out[4]= {5.641420, Null}

In[5]:= Rasterize[Notebook[{Cell@BoxData@boxes}], "Image"]; // AbsoluteTiming

Out[5]= {3.383325, Null}

In[6]:= boxes = ToBoxes[g]; // AbsoluteTiming

Out[6]= {1.314225, Null}

This tells us that:

- generating the graph is instantaneous
- laying out the graph takes about 4.4 seconds
- generating the box form of the graph takes about 1.2 seconds. We get 5.6 the first time because this includes layout out the graph too, but notice that the second ToBoxes runs in only 1.3 seconds again. The layout was probably cached.
- Compressing the boxes, sending them to the Front End, and rendering them takes about 3.3 seconds.

All this adds up to 9 seconds in total. Measuring with a stopwatch gives me about 8 seconds, confirming that this way of benchmarking is correct (at least for estimation). Note that this must be measured in a fersh kernel, or with a newly generated graph, to avoid caching the layout! It's easy to forget about wall time while only looking at AbsoluteTiming's output.

Now let's try GraphEmbedding again:

In[7]:= GraphEmbedding[g]; // AbsoluteTiming

Out[7]= {4.169074, Null}

Well, this function doesn't use the supposedly cached graph layout. Why?

**Is this a bug?**