I understand your concerns about boost... let my try and allay them:
A quick browse of the boost graph headers shows there are some dependencies on other parts of boost, but I haven't found any reference to the dreaded smart_ptr stuff yet ;-). Hopefully, I could pare it down to a minimal set of headers (not including smart_ptr and so on) before adding anything to the inkscape code base.
Regarding the build process the graph examples compile with (assuming headers in the include path):
g++ example.cpp -o example
As for optimisation, the algorithms we're talking about are quite computationally intensive and boost is written in a heavily templated generic style. I think that's the only reason they recommend optimisation. Surely inkscape binary distributions are compiled with optimisation on anyway, right?
I was a bit worried about bloat and compilation speed but the examples which use the kind of stuff I need compile down to <100k (on x86 linux) in a few seconds. I'm guessing, but I think this would be comparable to an stl based implementation of the same thing.
Regarding "mismatch of code" with the rest of the project, I really would just be using the graph datastructures and algorithms. I don't have any intention of using any of the fancy stuff that fundamentally affects coding style (like the aforementioned smart_ptrs or the lambda stuff).