We adapt the compact routing scheme by Thorup and Zwick to optimize it for power-law graphs. We analyze our adapted routing scheme based on the theory of unweighted random power-law graphs with fixed expected degree sequence by Aiello, Chung, and Lu. Our result is the first theoretical bound coupled to the parameter of the power-law graph model for a compact routing scheme. In particular, we prove that, for stretch 3, instead of routing tables with [(O)\tilde](n^1/2)\tilde{O}(n^{1/2}) bits as in the general scheme by Thorup and Zwick, expected sizes of O(n ^γ logn) bits are sufficient, and that all the routing tables can be constructed at once in expected time O(n ^1 + γ logn), with g = \fract-22t-3+e\gamma=\frac{\tau-2}{2\tau-3}+\varepsilon, where τ ∈ (2,3) is the power-law exponent and ε> 0. Both bounds also hold with probability at least 1 − 1/n (independent of ε). The routing scheme is a labeled scheme, requiring a stretch-5 handshaking step and using addresses and message headers with O(lognloglogn) bits, with probability at least 1 − o(1). We further demonstrate the effectiveness of our scheme by simulations on real-world graphs as well as synthetic power-law graphs. With the same techniques as for the compact routing scheme, we also adapt the approximate distance oracle by Thorup and Zwick for stretch 3 and obtain a new upper bound of expected [(O)\tilde](n^1+g)\tilde{O}(n^{1+\gamma}) for space and preprocessing.