We consider a facility layout problem with the objective of minimizing total transportation distance, which is the sum of rectilinear distances between facilities weighted by the frequency of trips between the facilities. It is assumed that facilities are required to have rectangular shapes and there is no empty space between the facilities in the layout. In this study, a graph theoretic heuristic is developed for the problem. In the heuristic, planar graphs are constructed to represent adjacencies between the facilities and then the graphs are converted to block layouts on a continual plane using a layout construction module. (Therefore, each graph corresponds to a layout.) An initial layout is obtained by constructing a maximal weighted planar graph and then the layout is improved by changing the planar graph. A simulated annealing algorithm is used to find a planar graph which gives the best layout. To show the performance of the proposed heuristic, computational experiments are done on randomly generated test problems and results are reported.