The graph-theoretical thickness (shortly thickness)of graph G,
denoted by Φ(G), is the minimum number of planar subgraphs into
which the graph can be decomposed, and a graph that can be
drawn in the plane without any of its edges intersecting is c
alled a
planar graph. determining the thickness of a given graph is known
to be an NP-complete problem.
In this paper we introduce an application heuristic algorithm for
determining the thickness. Our algorithm is based on simulated
annealing optimization scheme which provide the results of the
New-thick (1). We show that the simulated annealing is a efficient
method to obtain good approximation for the thickness when the
number vertices are at most 30 otherwise it is slower.
Finally, we apply this algorithm on the heuristic algorithm Newthick
and we show that the algorithm produces a good
approximation and optimization solution for the thickness, and we
program this algorithm with C++, and running it by laptop has
RAM 2GB and CPU 2.27GHZ.
