Depending on your application, if you're interested in A* you may be interested in using Theta* instead. It's not much more difficult to implement but provides much shorter paths if one does not need to remain on the edges in the graph.

Take a look at the explanation and figures here: http://aigamedev.com/open/tutorials/theta-star-any-angle-pat... for more information.