A new operation, referred to as the ¦)-operation, for replacing edges of the maximal planar graph is presented. Cases of this operation are discussed. It is then used to develop two graph-theoretic improvement procedures for solving facilities layout problems. Both procedures can be employed to improve solutions of any existing graph-theoretic construction heuristic. A computational experiment is reported for a series of test problems which indicates that both procedures can considerably improve the initial solutions in a cost-effective manner. Since they are simple and effective, realistically sized facilities layout problems can be solved efficiently by their use.
