I am using java2d to draw a simple graph at the moment I have implemented picking by calling contains(MousePoint) for each object/shape, this works but scales linearly.
Is there a more efficient method for picking in java2d?
Yes, although the full answer would be too long for this space.
First of all, unless you have a lot of nodes, then linear will most likely be fine, and you shouldn't change anything unless performance is already seen to suffer.
Second, what you want, in general, is to apply some sort of hierarchical decomposition, such as a quadtree. This is a way of using more memory (and more time up front, amortized during searches) to eliminate items from consideration in a so-called "broad phase". Some diligence on the web will help, as will the book "Real-Time Collision Detection", by Christer Ericson.