When designing a facility layout it is desirable to obtain an optimum design which satisfies certain necessary relationships among departments. Recent research has indicated that applying graph theory to the layout problem can result in the development of improved solutions, but little can be found to indicate how much better the resultant solutions are. The objectives of this paper are to develop a graph theory approach based on research experience and suggestions of Moore, Carrie and Seppanen, to develop a general computer program implementing the procedure and to compare its performance with that of CRAFT, CORELAP and ALDEP. The comparisons are based upon the adjacency relationships satisfied in the resultant layouts. The procedure finds the graph G equivalent to the problem being solved and then generates one of its maximal spanning trees, which after being transformed to its ‘string’ equivalent, is used to extract a maximal planar sub-graph of G. The dual of this sub-graph represents the desired solution. This approach allowed two usual problems to be avoided; firstly, testing for planarity of a graph and secondly, testing for cycles in the generation of a maximal spanning tree. The resultant PL/1 program, called graph and string-oriented layout (GASOL), is used to solve a standard set of eight problems, i.e. Nugent's problem set. The generated layouts were then compared to those obtained by CRAFT, CORELAP, and ALDEP on the same set of problems. The results of these comparisons showed that GASOL satisfies more of the number of layout adjacencies and achieves higher ‘scored’ layout arrangements than either CRAFT, CORELAP, or ALDEP, As a consequence more flow or material handling volume is included in a GASOL layout. The increase in the number of adjacencies ranges from a low of 53% to a high of 63.1%. This computational experience suggests that a graph theory approach to the layout problem can provide significantly improved results over those obtained by these existing computerized layout routines, with moderately increased computational times.