Software deployment process is a sequence of related activities for installing an already developed application into its target environment, and bringing it into an executing state. For complex component-based applications that should be deployed into a large distributed environment, several deployment configurations are typically possible. These deployment configurations can have significant impacts on the application?s quality of service properties such as reliability. In distributed systems, the reliability of the application is highly dependent on the reliability of its network, and network failures can have adverse effects on the application?s reliability. Thus, one possible way to increase the reliability of a distributed component-based application is to deploy it so that the communications among its components are done as local as possible. In this paper, a graph-based deployment planning approach is proposed for this purpose.