Abstract
Graphs provide an intuitive way of representing connected or interacting entities [GY99]. One can very easily model and study various real-life and scientific structures using graphs, e.g., web pages linking to each other [BV03], friendship in social networks, the relative location of image features [DPZ01], transportation networks, electric circuits and computer network topologies. Mathematicians have been studying graph theory since the 18th century, starting with a published paper on the Seven Bridges of Konigsberg by Euler [Big93].