The maximum #vertices/#edges estimates are too conservative.

[pstutz]

The graph size estimation probably assumes that all memory usage is only due to the vertices. A better estimate of the constant overhead would make the max vertex/edge estimates more reliable.

[troxler]

better estimate of the constant overhead

Any idea on how to achieve that?

When I tested the estimation, I found it to be quite reliable. Also it should be more accurate when approaching the maximum amount of available memory.