ON FINDING A BICONNECTED SPANNING PLANAR SUBGRAPH WITH APPLICATIONS TO THE FACILITIES LAYOUT PROBLEM

The BSPS problem is to find a planar and biconnected spanning subgraph of a general graph. This problem is related to the planarization prob lem which seeks a planar spanning subgraph with a maximum number of ed ges, Like the planarization problem, BSPS has applications in facility layout problems, which seek the best arrangement of facilities on a s hop floor, such that the adjacency of facilities which share material flows is maximized. In this paper we prove that the BSPS problem is NP -hard, We develop a heuristic algorithm and present empirical results that show this heuristic to be successful in most cases.