Hi Tiago,
Sorry for my late reply, but I only got the chance to try it now and
it works
Great. 
One more stupid question: can one use the pre-compiled binaries to
bypass the problem with gcc and have multi-threaded parallel algorithm
support on graph-tool?
In principle yes, if one links to a static version of libgomp (GCC's
implementation of openmp) that works. But note that there's yet a much
more severe problem with openmp and GCC:
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33361
This bug actually causes GCC to crash when compiling graph-tool... I
guess openmp is still a quite young addition to GCC and it needs to
stabilize a bit.
Cheers,
Tiago