Only one approach to obtain approximations for the thickness problem is known in the literature: extract maximal planar subgraphs from the origi-nal graph until the remaining graph is planar. The algorithms differ by the method used in planar subgraph search from the original graph and by the optimization of the extracted subgraphs.
4.3. ALGORITHMS FOR THICKNESS Next we describe the basic approach to get approximations for thickness.
The extraction method was first studied by Cimikowski [32] and Mutzel et al.
[101]. For a detailed description of the extracting method see Algorithm 4.6 (Thick). Step 4 of the algorithm is usually given as “find a maximal/maximum planar subgraph” instead of finding just a planar subgraph.
Thick(G= (V, E)) 1 P ← ∅ and t←1.
2 while E 6=∅
3 do find a planar subgraphG0 = (V, Et) of G;
4 E ←E\Et;
5 P ←P ∪ {Et};
6 t←t+ 1;
7 return P;
Algorithm 4.6: Basic structure of the extraction algorithm for the thickness problem.
The running time of Thick depends highly on the method used in Step 3.
It is clear that any algorithm that approximates thickness has at least linear running time, since all edges have to be considered.
Cimikowski [32] applied the maximal planar subgraph algorithm by Cai et al. [25] to extract subgraphs. We will denote this algorithm byHTin Chapter 8. Further, Cimikowski experimented a maximal planar subgraph algorithm by Kant [72] based on vertex addition approach and P Q-trees. These two methods are also used by Mutzel et al. [101].
Basically, the larger subgraphs we can extract from the input graph, the better approximation for thickness we can obtain. Of course, this method does not necessarily lead to optimal solution, as shown by Mutzel et al. [101]
by giving a counterexample. Recently, Kawano and Yamazaki [74] showed that it makes no difference from the theoretical point of view whether we extract maximal planar subgraphs or maximum planar subgraphs from the input graph. Both approaches guarantee only solutions that are Ω(logn) times the optimal for a graph with n vertices. The graph used in this construction was quite different from the graphs used in any practical applications.
After obtaining an initial solution byThick, it is possible to try to optimize this solution by edge removal and insertion operations. Poranen [108] gave a simulated annealing algorithm that can be used to decrease the number of
planar subgraphs. A planar partition of the edges of a nonplanar graph G = (V, E) is a partition of E, where each subset induces a planar subgraph. The simulated annealing algorithm for determining the thickness of a graph (SA), gets as input a planar partition of the edges. SA makes a local optimization guided by the simulated annealing scheme to decrease the number of planar subgraphs. The number of planar subgraphs can only decrease, worsening the result is not allowed.
The neighborhood structure for a nonplanar graph G = (V, E) is defined as follows. Let P = {E1, E2, . . . , Ek} and P0 = {E10, E20, . . . , Ek0} be planar partitions of the edges of G and let ei be an edge of Ei and ej an edge ofEj, wherei6=j. The planar partitions P and P0 are neighbors provided that
• P0 can be obtained from P by swapping the edges ei and ej, or
• P0 can be obtained from P by movingei toEj.
Notice that since we assume partitions to be planar, swapping and moving the edges are not allowed to violate the planarity of the subsets. See Algorithm 4.7 (SA) for a detailed description of the method. Algorithm 4.6 can be used to construct the initial solution forSA.
The general ideology behind SA is that when the sizes of the subsets of an edge partition have as high a deviation as possible, we have good chances to move edges from the smaller subsets to the larger ones. And finally, when the last edge of a subset is successfully moved to any other subset of the edge partition, we have decreased the number of planar subgraphs and obtained a better approximation for thickness. The empty subset is removed from the partition.
Increasing the deviation of the sizes of the subsets is done by choosing two edges randomly from distinct subsets. SA tries to move the edge from the smaller subset to the larger one without violating the planarity of the subset.
If this is not possible, SA tries to swap the edges. If the swap is not possible, SA checks if it is possible to move the edge from the larger set to the smaller one.
To check if this move is possible, we calculate the standard deviations of the sizes of the subsets of the original partition and the partition after the move. For an edge partition P ={Ei, E2, . . . , Ek}, the deviation is calculated from the formula
deviation({E1, E2, . . . , Ek}) = s
Pk
i=1(|Ei| −PAVE)2
k ,
4.3. ALGORITHMS FOR THICKNESS
SA(G= (V, E), P ={E1, E2, . . . , Ek})
1 select a cooling ratioα and an initial temperature t0;
select a frozen temperature tl and an equilibrium detection rater;
t←t0 and e←0;
2 while t≥tl and |P|> lower bound
3 do while e≤r and |P|>lower bound
4 e←e+ 1;
5 randomly select two edgesei and ej from distinct subsets Ei
and Ej of P with |Ei| ≤ |Ej|;
6 if Ej ∪ {ei} is planar
7 then Ej ←Ej∪ {ei}and Ei ←Ei\ {ei};
8 if Ei is empty
9 then remove Ei from P;
10 else if Ej\ {ej} ∪ {ei} and Ei\ {ei} ∪ {ej} are planar
11 then Ej ←Ej\ {ej} ∪ {ei} and Ei ←Ei\ {ei} ∪ {ej};
12 else let δ←deviation(P)−deviation(P0) where P0 is the edge partition where ej is moved to Ei;
13 if δ≤0 and Ei∪ {ej}is planar
14 then P ←P0;
15 else generate a random real i, 0 ≤i≤1;
16 if i≤e−δ/t and Ei∪ {ej} is planar
17 then P ←P0;
18 t←αt;
19 e←0;
20 return P;
Algorithm 4.7: SA for determining the thickness of a graph.
wherePAVE is the average size of the subsets.
The deviation can increase, decrease or keep unchanged when we move an edge from the larger set to the smaller one. The deviation is used to test if the move is acceptable as follows. LetP and P0 be the partitions before and after a move, respectively, and letδ =deviation(P)−deviation(P0). The following simple rule is now applied:
• Ifδ ≤0, the move is accepted.
• Otherwise, a random real i, 0≤ i ≤1, is generated. If i≤ e−δ/t, where t is the current temperature, the move is accepted.
The running time of SAdepends only on the annealing parameters and the implementation of the planarity testing algorithm. If the equilibrium detection rate is set to be equal with the number of edges in the input graph, SA runs inO(nm) time for a graph withn vertices andm edges.
In general, SA can improve the solutions of the other heuristics almost always, as demonstrated in Chapter 8.
Furthermore, a genetic algorithm is implemented [88] for approximating the thickness of a graph. The algorithm is based on dividing the input graph into planar subgraphs and one nonplanar subgraph. After initialization it uses local optimization guided by the genetic operations to planarize the last subset. The number of planar subgraphs does not change dynamically during the execution of the algorithm; if a predefined limit exceeds, the number of planar subgraphs is increased by one and again the last nonplanar subset is planarized by the genetic operations.