Just a guess here, but depending on how you are measuring the performance, you might be spending a lot of time actually drawing the graph path -- which is likely to cost more than the actual search.
Try adding timing metrics that exclude the drawing process before compare. Note of course, that your dependency will be not only on the number of vertices, but also, the number of edges in your graph.