The optimal PMU locations to collect voltage phase angle measurements for detecting line outages in wide-area transmission networks are investigated. The problem is established as one of maximizing the minimum distance among the voltage phase angle signatures of the outages, which can be equivalently formulated as an integer programming problem. Based on a greedy heuristic and a linear programming relaxation, a branch and bound algorithm is proposed to find the globally optimal PMU locations. Using this algorithm, the optimal tradeoff between the number of PMUs and the outage detection performance is characterized for IEEE 14, 24 and 30 bus systems. The algorithm is shown to find the globally optimal PMU locations in a small number of iterations. It is observed that it is sufficient to have roughly one third of the buses providing PMU measurements in order to achieve the same outage detection performance as with all the buses providing PMU measurements.