A simulated annealing algorithm for determining the thickness of a graph

The thickness of a graph is the minimum number of planar subgraphs into which the graph can be decomposed. Determining the thickness of a given graph is known to be an NP-complete problem. In this paper we introduce a new heuristic algorithm for determining the thickness of a graph. Our algorithm is based on the simulated annealing optimization scheme. We compare the quality of the solutions and running times of our algorithm against previously tested heuristic algorithms. We show that the simulated annealing is a fast and efficient method to obtain good approximations for the thickness of a graph. We also give a new upper bound for the thickness of complete tripartite graphs, whose vertex sets are of equal size. (c) 2004 Elsevier Inc. All rights reserved.