An efficient overlap removal algorithm in the context of macrocell placement is presented in this paper. The algorithm works on a novel augmented constraint graph and removes overlap in the presence of fixed location, spacing and boundary constraints imposed on macro cells. We propose a modifed Parallel Plane Shadowing Sweep algorithm for creation of constraint graph and an augmentation scheme to handle constraints effectively. The spatial relations that exist among the macro cells in an overlapping placement is retained in the overlap free placement. A peripheral placement of macro cells is made feasible by utilizing the information in the constraint graph to compact the macro cells towards the periphery in conjunction with the legalization of the macro cells. Experimental results obtained with and without compaction on randomly generated testcases based on GSRC floorplanning benchmarks is presented. The run-time of the algorithm has been shown to scale linearly with increasing number of blocks.