Remarks on the thickness and outerthickness of a graph

The thickness of a graph is the minimum number of planar subgraphs into which the graph can be decomposed. The thickness of complete bipartite graphs Km,n is known for almost all values of m and n. In this paper, we solve the thickness of complete bipartite graphs for unknown cases m < 30, m ≤ n. The new solutions coincide with the general formula and they were obtained by using a simulated annealing algorithm. The outerthickness of a graph is the minimum number of outerplanar subgraphs into which the graph can be decomposed. We give lower and upper bounds for outerthickness in the terms of the minimum and maximum degree of a graph. Let δ be the minimum degree and Δ the maximum degree of a graph G. We show that the following bounds hold for outerthickness: [δ/4] ≤ Θo(G) ≤ [Δ/2]. We also discuss the possibility of determining the upper bound for outerthickness using the number of edges of a given graph.