Article ID: | iaor1999540 |
Country: | Netherlands |
Volume: | 94 |
Issue: | 1 |
Start Page Number: | 97 |
End Page Number: | 105 |
Publication Date: | Oct 1996 |
Journal: | European Journal of Operational Research |
Authors: | Goldschmidt Olivier, Yu Gang, Takvorian Alexis |
Keywords: | graphs |
The BSPS problem is to find a planar and biconnected spanning subgraph of a general graph. This problem is related to the planarization problem which seeks a planar spanning subgraph with a maximum number of edges. Like the planarization problem, BSPS has applications in facility layout problems, which seek the best arrangement of facilities on a shop 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.