Graph theoretic and combinatorial problems arise in several traditional and emerging scientific disciplines such as VLSI design, optimization, databases, and computational biology. Some examples include phylogeny reconstruction [65,66], protein-protein interaction networks [89], placement and layout in VLSI chips [59], data mining [52,55], and clustering in semantic webs. Graph abstractions are also finding increasing relevance in the domain of large-scale network analysis [28,58]. Empirical studies show that many social and economic interactions tend to organize themselves in complex network structures. These networks may contain billions of vertices with degrees ranging from small constants to thousands [14,42].