The performance of cognitive networks (CNs) has been significantly improved by deploying a third-party, namely relay, to assist the direct communication. However, under a limited transmit power governed by the maximum tolerable interference at the primary network, the cognitive relay network still suffers a performance loss compared to its non-cognitive counterpart. To alleviate this shortcoming, this paper has pro-posed a technique to optimally deploy the relay in CNs. In particular, by assuming the decode-and-forward (DF) relay, we first derive an exact expression for the outage probability (OP) of CNs with spectrum-sharing environment over Nakagami-m channels. Then, using the exact formula, we obtain the asymptotic OP expression which further reveals the impact of networks' parameters on the performance. In addition, the optimal relay placement, i.e., minimizing the system OP, is also investigated by utilizing the asymptotic OP result. We have shown through some representative scenarios that given a fixed coordinate of a primary receiver, the optimal relay deployment significantly outperforms the two conventional approaches, i.e., uniform and random topologies.