In recent years new research studies have appeared that concern the issue of network planning in LTE-Advanced. In this paper, the coverage problem in LTE-Advanced relay networks is formulated based on integer linear programming (ILP). We propose the Enhanced tree (E-Tree) algorithm to place the evolved Node B (eNB) and relay station (RS) at the location which has the lowest construction cost. The goal is not only satisfy the minimum requirement but also meet the two hop relaying limitation in LTE-Advanced networks. The E-Tree algorithm is proposed based on graph theoretic technique, and analyzed with the simulation results. The simulation results show that the proposed algorithm provides a rapid planning method and the lowest construction cost with various network environment.