# Algorithm 797: Fortran Subroutines for Approximate Solution of Graph Planarization Problems Using GRASP.

1. INTRODUCTIONA graph is said to be planar if it can be drawn on the plane in such a way that no two of its edges cross. Given a graph G = (V, E) with vertex set V and edge set E, the objective of graph planarization is to find a minimum cardinality subset of edges F [subset or equal to] E such that the graph G' = (V, E\F) resulting from the removal of the edges F from G is planar. This problem is also known as the maximum planar subgraph problem. A maximal planar subgraph is a planar subgraph G' = (V', E') of G = (V, E), such that the addition of any edge [element of] C E\E' to G' destroys the planarity of the subgraph.

Graph planarization is known to be NP-hard [Liu and Geldmacher 1977], and most algorithms to date attempt to find good approximate solutions. Several graph planarization heuristics have been proposed in the literature. Jayakumar et al. [1989] describe two O([|V|.sup.2]) planarization algorithms, based on the Lempel, Even, and Cederbaum planarity testing algorithm [Lempel et al. 1966]. Cai et al. [1993] proposed an O(|E|log|V|) algorithm for finding a maximal planar subgraph based on the Hopcroft and Tarjan planarity testing algorithm [Hopcroft and Tarjan 1974]. Another O(|E|log|V|) algorithm was also proposed by Di Battista and Tamassia [1989], based on an O(log|V|) time-per-operation strategy to the problem of maintaining a planar graph under edge additions.

Takefuji and Lee [1989] described a parallel heuristic for planarization based on neural networks. They use an arbitrary sequencing of the vertices, placing them along a line, followed by the use of a neural network for determining two sets of edges that may be represented without crossings above and below that line, respectively. The two-phase approach of Takefuji and Lee was extended and improved by Goldschmidt and Takvorian [1994]. Junger and Mutzel [1996] designed an exact branch-and-cut algorithm for the maximum planar subgraph problem using facet-defining inequalities. A heuristic based on the branch-and-cut algorithm stops with a feasible, though not necessarily optimal, solution.

Resende and Ribeiro [1997] further extended the two-phase approach, applying the framework of the GRASP (Greedy Randomized Adaptive Search Procedure) metaheuristic. The Fortran subroutines described in this article are an implementation of that GRASP.

We next describe the organization of this article. Section 2 describes the GRASP for graph planarization. The Fortran implementation is outlined in Section 3, and its usage is described in Section 4. In Section 5, we present some computational results illustrating the effectiveness of this approximate solution procedure.

2. GRASP FOR GRAPH PLANARIZATION

A GRASP [Feo and Resende 1995] is an iterative process, where each iteration consists of two phases: construction and local search. The construction phase builds a feasible solution, whose neighborhood is explored by local search. The best solution over all iterations is returned as the result. Figure 1 illustrates a generic GRASP implementation in pseudocode. The GRASP takes, as input, parameters for setting the candidate list size, maximum number of iterations, and the seed for the random-number generator. After reading the instance data (line 1), the iterations are carried out in lines 2-6. Each iteration consists of the construction phase (line 3), the local search phase (line 4), and, if necessary, the incumbent solution update (line 5).

Fig. 1. A generic GRASP pseudocode.

procedure GRASP(ListSize, MaxIter, RandomSeed) 1 Input Instance (); 2 do k = 1,..., MaxIter [right arrow] 3 ConstructGreedyRandomizedSolution (ListSize, RandomSeed); 4 LocalSearch(BestSolutionFound); 5 UpdateSolution(BestSolutionFound); 6 od; 7 return BestSolutionFound endGRASP;

In the graph planarization problem, the construction phase (see Figure 2) of each GRASP iteration consists in devising a sequence [Pi] of the set of vertices V of the input graph G. The vertices of G are placed on a line according to this sequence [Pi]. The procedure takes as input the graph G = (V, E) to be planarized, the restricted candidate list (RCL) parameter a (0 [is less than or equal to] [Alpha] [is less than or equal to] 1), and a seed for the pseudorandom-number generator. Let [deg.sub.G](v) be the degree of vertex v with respect to G, and let d = [min.sub.v [element of] v]{[deg.sub.G](v)} and d = [max.sub.v [element of] v]{[deg.sub.G](v)}. The first vertex in the sequence is determined in lines 1-3, where all vertices having degree in the range [d, [Alpha](d - d) + d] are placed in the RCL and where a single vertex is selected at random from the list. The working vertex set V and graph [G.sub.1] are defined in line 4.

Fig. 2. Pseudocode of GRASP construction phase.

procedure ConstructGreedyRandomizedSolution([Alpha],seed,V,E,[Pi]) 1 d = [min.sub.v [element of] v]{[deg.sub.G](v)}; d = [max.sub.v [element of] v]{[deg.sub.G](v)}; 2 RCL :{v [element of] V : d [is less than or equal to] [deg.sub.G] (v) [is less than or equal to] [Alpha] (d - d) + d}; 3 [v.sub.1] = random(seed, RCL); 4 V = V \ {[v.sub.1]}; [G.sub.1] : graph induced on G by V; 5 do k = 2,...,|V| [right arrow] 6 d = [min.sub.v [element of] v]{[deg.sub.Gk-1] (v)}; d = [max.sub.v [element of] v]{[deg.sub.Gk-1] (v)}; 7 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 8 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 9 fi; 10 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 11 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 12 fi; 13 [v.sub.k] = random(seed, RCL); 14 V = V \ {[v.sub.k]}; [G.sub.k] = graph induced on G by V; 15 od 16 return [Pi] = ([v.sub.1],[v.sub.2],...,[v.sub.|v|]) end ConstructGreedyRandomizedSolution;

The loop from line 5 to 15 determines the sequence of the remaining |V| -- 1 vertices. To assign the kth vertex (iteration k of the loop) two cases can occur. Define [G.sub.k] to be the graph induced on G by V\{[v.sub.1], [v.sub.2], ... , [v.sub.k]}. Let [ADJ.sub.Gk-1]([v.sub.k-1]) be the set of vertices of [G.sub.k-1] adjacent to [V.sub.k-1] in G. The RCL is made up of all vertices in [ADJ.sub.Gk-1] ([V.sub.k-1]) having degree in the range [d, [Alpha](d - d) + d] in [G.sub.k]. Otherwise, if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the RCL is made up of all unselected vertices having degree in the range [d, [Alpha](d - d) + d] in [G.sub.k]. In line 13, the kth vertex in the sequence is determined by selecting a vertex, at random, from the RCL. The greedy function is adapted in line 14 where the working vertex set and graph are updated. The vertex sequence [Pi] = ([v.sub.1], [v.sub.2], ... , [v.sub.|v|]) is returned, where [Pi](v) denotes the relative position of vertex v c V within vertex sequence II. Furthermore, let [e.sub.1] = (a, b) and [e.sub.2] = (c, d) be two edges of G, such that, without loss of generality, [Pi](a) [is less than] [Pi](b) and [Pi](c) [is less than] [Pi](d). These edges are said to cross with respect to sequence [Pi] if [Pi](a) [is less than] [Pi](c) [is less than] [Pi](b) [is less than] [Pi](d) or [Pi](c) [is less than] [Pi](a) [is less than] [Pi](d) [is less than] [Pi](b).

The vertex ordering obtained at the end of the construction phase may be improved by attempting to reduce the number of crossing edges by locally searching a neighborhood of the current vertex sequence prior to the second phase. We next describe such a local search procedure. To do so, let us define the neighborhood N([Pi]) of the vertex sequence [Pi] to be formed by all vertex sequences [Pi]' differing in exactly two positions, i.e.,

N([Pi]) = {[Pi]' = ([v'.sub.1], [v'.sub.2], ... , [v'.sub.|v|]): [v'.sub.i] = [v.sub.i], [inverted A]i [is not equal to] j, k, [v'.sub.j] = [v.sub.k], [v'.sub.k] = [v.sub.j]}.

Let [X.sub.([Pi])] be the number of edge-pairs that cross with respect to vertex sequence [Pi]. The pseudocode in Figure 3 describes the local search procedure used in the GRASP. In our implementation, we use a slightly more restricted neighborhood, in which only consecutive vertices can be exchanged.

Fig. 3. Pseudocode of GRASP local search phase.

procedure LocalSearch(V,E,[Pi]) 1 do [Pi] is not locally optimal [right arrow] 2 Find [Pi]' [element of] N([Pi]) such that X([Pi]') [is less than] X([Pi]); 3 H = H'; 4 od 5 return [Pi] = ([v.sub.1],[v.sub.2],...,[v.sub.|v|]) end LocalSearch;

Let H = (E, I) be a graph where each of its vertices corresponds to an edge of the input graph G. Vertices [e.sub.1] and [e.sub.2] of H are connected by an edge if the corresponding edges of G cross with respect to sequence [Pi]. A graph is called an overlap graph if its vertices can be placed in one-to-one correspondence with a family of intervals on a line. Two intervals are said to overlap if they cross and none is contained in the other. Two vertices of the overlap graph are connected by an edge if and only if their corresponding intervals overlap. Hence, the graph H as constructed above is the overlap graph associated with the representation of G defined by sequence [Pi].

Following Goldschmidt and Takvorian [1994], the next phase of our procedure consists in two-coloring a maximum number of the vertices of the overlap graph H such that each of the two color classes B (blue) and R (red) forms an independent set. Equivalently, the second phase seeks a maximum induced bipartite subgraph of the overlap graph H, i.e., a bipartite subgraph having the largest number of vertices. This problem is equivalent to drawing the edges of the input graph G above or below the line where its vertices have been placed, according to sequence II. Since the decision version of the problem of finding a maximum induced bipartite subgraph of an overlap graph is NP-complete [Sarrafzadeh and Lee 1989], a greedy algorithm is used in GT to construct a maximal induced bipartite subgraph of the overlap graph. This algorithm finds a maximum independent set B [subset or equal to] E of the overlap graph H = (E, I), reduces the overlap graph by removing from it the vertices in B and all edges incident to vertices in B, and then finds a maximum independent set R [subset or equal to] E \ B in the remaining overlap graph H' = (E \ B, I'). The two independent sets obtained induce a bipartite subgraph of the original overlap graph, not necessarily with a maximum number of vertices. This procedure has polynomial time complexity, since finding the maximum independent set of an overlap graph has been shown by Gavril [1973] to be polynomially solvable in time O(|[E.sup.3]|), where |E| is the number of vertices of the overlap graph H = (E, I) (see also Golumbic [1980] for another description of this algorithm). Pseudocode for the two-coloring procedure is given in Figure 4.

Fig. 4. Pseudocode of the two-coloring procedure.

procedure TwoColoring(V,E,[Pi],B,R) 1 BuildOverlapGraph(V, E, [Pi], I); 2 FindMaxIndependentSet (E, I, B); 3 ReduceOverlapGraph(E, I, B, I'); 4 FindMaxIndependentSet (E \ B, I', R); 5 return B, R end TwoColoring;

The two-coloring heuristic outputs three edge sets: B (blue edges), R v(red edges), and P (the remaining edges, which we refer to as the pale edges). By construction, B, R, and P are such that no red or pale edge can be colored blue. Likewise, pale edges cannot be colored red. However, if there exists a pale edge p [element of] P such that all blue edges that cross with p (let [B.sub.p] [subset or equal to] B be the set of those blue edges) do not cross with any red edge r [element of] R, then all blue edges b [element of] [B.sub.p] can be colored red and p can be colored blue. This reassignment of color classes increases the size of the planar subgraph by one edge. Figure 5 shows pseudocode for procedure Enlarge-Planar that seeks pale and blue edges allowing the above color class reassignment and enlarges the planar subgraph when such edges are encountered. The pale edges are scanned in do loop 1-12, while loop 3-10 scans the blue edges to construct the set [B.sub.p], whose elements are saved in line 5. If a blue edge b E [element of] [B.sub.p] crosses any red edge, the set [B.sub.p] is discarded (line 7), and a new pale edge is scanned. If no edge b [element of] [B.sub.p] crosses red edges, then all blue edges b [element of] [B.sub.p] are colored red, and the pale edge p is colored blue in line 11. This procedure has time complexity O(|[E.sup.3]|).

Fig. 5. Pseudocode of local search procedure to enlarge planar subgraph.

procedure EnlargePlanar(B, R, P, V) 1 do p [element of] P [right arrow] 2 [B.sub.p] = 0; 3 do b [element of] B [right arrow] 4 if p and b cross [right arrow] 5 [B.sub.p] = [B.sub.p] [union] {b}; 6 do r [element of] R [right arrow] 7 if r and b cross [right arrow] goto 12 fi; 8 od; 9 fi; 10 od; 11 (B, R, P) = (B [union] {p} \ [B.sub.p], R [union] [B.sub.p], P \ {p}); 12 od; 13 return B, R end EnlargePlanar;

By incorporating the two-coloring heuristic and the graph-enlarging procedure to the construction and local search phases, we have a GRASP for graph planarization, whose pseudocode is given in Figure 6.

Fig. 6. Pseudocode of GRASP for graph planarization.

procedure GRASPforGP ([Alpha],seed,MaxIter,V ,E,II*,R*) 1 do k = 1, 2, ...,MaxIter [right arrow] 2 ConstructGreedyRandomizedSolution([Alpha],seed,V ,E,II); 3 LocalSearch(V,E,II); 4 TwoColoring(V,E,II,B,R); 5 P = E\ (B [union] R); 6 EnlargePlanar(B,R,P,V); 7 UpdateSolution(II,B,R,II*,B*,R*); 8 od 9 return II*, B*, R* end GRASPforGP;

The procedure is repeated MaxIter times. In each iteration, a greedy randomized solution (vertex sequence H) is constructed in line 2. In line 3, the local search attempts to produce a vertex sequence that has fewer edge-pair crossings than the one generated in line 2. The vertex sequence H is given as input to the two-coloring heuristic in line 4 to produce a planar subgraph of G. In lines 5 and 6 the procedure to enlarge the current planar subgraph is applied. If the cardinality of the edge-set of the subgraph found in line 6 is the largest found so far, it is recorded in line 7.

3. DESIGN AND IMPLEMENTATION OF THE SUBROUTINES

The code is implemented in ANSI standard Fortran 77, and runs without any modifications on UNIX environments. It has also run on other environments with little or no change. Input, output, variable, and array declarations and parameter settings are all performed in a separate driver module. Therefore, usage and experimentation with the code are relatively simple.

The optimization package consists of three files: Makefile, driver, f, and gmpsg.f. Also included in the distribution is a sample input data file, sample.dat.

4. USAGE OF THE SUBROUTINES

The subroutines in file gmpsg.f carry out the approximate optimization of the maximum planar subgraph problem. The user interface with them is subroutine gmpsg, which must be called from a driver program. In addition to a number of auxiliary arrays, the driver passes (1) the following representation of the input graph

n: Number of nodes in graph

m: Number of arcs in graph

arc1: Integer array where arc1 (i) is node 1 of arc i

arc2: Integer array where arc2 (i) is node 2 of arc i

and (2) the following array dimensions:

nmax: Dimension of number of nodes declared in driver . f,

mmax: Dimension of number of arcs declared in driver . f.

The sample driver program for gmpsg included in the distribution (driver. f) is set for problems of dimension n [is less than or equal to] 200 vertices and m [is less than or equal to] 1600 edges. The input/output parameters that define Fortran input/output devices are set to the standard values in = 5 and iout = 6. These parameters can be set by the user for problems of different dimension or if an alternate input or output device is required.

All variables and arrays needed by subroutine gmpsg are defined in the main program in driver, f. Subroutines readp and outsol, also provided in driver . f, are examples of code that can be used for input and output, respectively. The driver program calls readp, which reads the input data and returns an error condition errcnd = 0 if no error in the input data is detected or errcnd = 1 if the declared number of nodes n [is greater than] nmax, errcnd = 2 if the declared number of arcs m [is greater than] mmax, or errcnd = 9 if the number of arcs provided in the input is less than the declared number of arcs m. If errcnd [is greater than] 0, then driver, f calls subroutine errmsg (provided in file gmpsg, f) which prints the error message, and execution is halted.

Five parameters that control the execution of the algorithm need to be set before the optimization module is called: alpha, the RCL parameter, is a real number that must satisfy 0 [is less than or equal to] alpha [is less than or equal to] 1; look4, a stopping parameter that forces GRASP to stop if a planar subgraph of size at least look4 is found, is an integer that must satisfy 0 [is less than or equal to] look4 [is less than or equal to] m; maxitr, the maximum number of GRASP iterations, is an integer such that maxitr [is greater than] 0; prttyp, the output option parameter, is an integer that is set to 0 (silent run; gmpsg does not write anything), 1 (gmpsg prints out solution improvements), or 2 (gmpsg prints out the solution found in each GRASP iteration); and seed, the pseudorandom-number generator seed, an integer such that 1 [is less than or equal to] seed [is less than or equal to] [2.sup.31] -- 1. The default settings for alpha, look4, maxitr, prttyp, and seed are, respectively, 0.1, m, 2048, 1, and 270001.

If errcnd = 0 is returned by readp, then driver, f calls the optimization subroutine gmpsg, which attempts to find a large planar subgraph of the input graph. Subroutine 9mpsg returns error condition errcnd indicating the status of the optimization. Error condition errcnd can have the following values:

errcnd = 1 if a n [is greater than] nmax;

errcnd = 2 if a m [is greater than] mmax;

errcnd = 3 if an input node is less than I or greater than m;

errcnd = 4 if alpha [is less than] 0 or alpha [is greater than] 1;

errcnd = 5 if look4 [is less than] 1 or look4 [is greater than] m;

errcnd = 6 if maxitr [is less than] 1;

errcnd = 7 if prttyp # 0,1,2;

errcnd = 8 if seed [is less than] 1 or seed [is greater than] 2147483647.

As an example, consider the instance g1 of dimension 10 vertices by 22 arcs (of Goldschmidt and Takvorian [1994]) with input file shown in Figure 7. Running the driver program using the default settings on instance g1 produces the output shown in Figure 8. The output lists each iteration for which an improving solution was found and describes the best solution found by listing the vertex permutation, and the blue and red arcs.

Fig. 7. Input file of graph planarization instance g1.

10 22 1 10 1 9 1 7 1 5 1 2 2 8 2 7 2 4 2 3 3 10 3 6 3 5 4 8 4 5 5 6 6 8 6 7 7 9 7 8 8 10 8 9 9 10

Fig. 8. Sample output of driver for graph planarization instance g1.

itr: 1 size: 20 improvement Execution terminated with no error. GRASP solution -- largest planar subgraph found in iteration: 1 size of largest planar subgraph: 20 avg size of planar subgraph: 19.2 blue arcs in planar subgraph: 16 red arcs in planar subgraph: 4 vrtx permut: 4 5 6 7 vrtx permut: 2 1 9 8 blue arcs: 1 2 3 5 7 blue arcs: 11 12 13 14 15 blue arcs: 16 17 18 19 21 blue arcs: 22 red arcs: 6 8 9 20

5. COMPUTATIONAL RESULTS

In this section, we illustrate the effectiveness of the subroutines by running the planarization procedure on a subset of the test problems used by Resende and Ribeiro [1997]. The experiment was limited to all of those test problems having at least 50 and at most 200 nodes with at most 750 arcs (a total of 51 instances). Each run of GRASP was done using the default parameter settings as defined in file driver, f of the distribution, i.e., alpha = 0.1, look4 = m, maxitr = 2048, prttyp = 1, and seed = 270001.

For each problem considered in the experiment, Tables I and II show the size (number of arcs) of the incumbent solution as a function of GRASP iterations. The incumbent solutions at iterations 2, 8, 32, 128, 512, and 2048 are listed. Figure 9 shows all incumbents at iterations 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, and 2048, as well as the average values of the incumbent solutions at those iterations (dotted line).

[Figure 9 ILLUSTRATION OMITTED]

Table I. Number of Arcs in Incumbent Solution as a Function of GRASP Iteration: Part 1

GRASP Iteration Name 2 8 32 128 512 2048 g2.cimi 160 160 165 165 165 165 g13 129 130 131 133 134 135 g14 141 141 143 143 143 143 g15 142 143 144 144 144 144 g16 184 187 190 190 191 193 g17 218 225 231 231 231 234 rg50.1 83 87 87 87 90 90 rg50.2 91 91 92 92 94 95 rg50.3 98 98 100 100 101 103 rg50.4 98 98 100 100 100 101 rg50.5 98 101 102 102 105 105 rg75.1 122 126 126 126 126 126 rg75.2 126 127 128 129 130 131 rg75.3 129 129 130 130 131 132 rg75.4 132 134 137 137 138 140 rg75.5 131 136 139 139 141 143 rg100.1 150 153 156 159 159 161 rg100.2 158 159 163 163 163 164 rg100.3 153 161 162 162 163 164 rg100.4 164 169 170 172 173 173 rg100.5 172 178 182 187 187 187 rg150.1 217 217 222 222 225 226 rg150.2 218 219 219 221 223 224 rg150.3 226 230 231 234 234 237 rg150.4 226 228 232 235 235 236 rg150.5 232 234 239 239 239 240 rg200.1 276 276 278 281 281 284 rg200.2 277 277 279 283 283 285 rg200.3 293 296 303 303 303 304 rg200.4 302 302 308 308 309 310 rg200.5 300 303 307 307 311 311

Table II. Number of Arcs in Incumbent Solution as a Function of GRASP Iteration: Part 2

GRASP Iteration Name 2 8 32 128 512 2048 tg100.1 239 247 257 257 258 258 tg100.2 227 247 252 253 265 265 tg100.3 237 248 252 252 256 262 tg100.4 235 244 249 254 254 262 tg100.5 241 244 244 250 252 254 tg100.6 231 231 237 242 244 253 tg100.7 219 229 240 244 244 246 tg100.8 227 232 236 247 247 248 tg100.9 230 235 235 237 239 241 tg100.10 219 229 230 235 236 244 tg200.1 463 463 477 477 491 491 tg200.2 435 460 471 478 480 488 tg200.3 463 478 485 495 502 504 tg200.4 462 469 469 476 488 493 tg200.5 448 458 463 473 474 486 tg200.6 462 462 462 468 477 482 tg200.7 426 431 446 450 452 466 tg200.8 443 449 458 461 492 492 tg200.9 434 451 451 453 461 465 tg200.10 443 443 443 461 468 468

REFERENCES

CAI, J., HAN, X., AND TARJAN, R. E. 1993. An O(m log n)-time algorithm for the maximal planar subgraph problem. SIAM J. Comput. 22, 6 (Dec. 1993), 1142-1162.

DI BATTISTA, G. AND TAMASSIA, R. 1989. Incremental planarity testing. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (FOCS '89, Research Triangle Park, NC, Oct. 30-Nov. 1) IEEE Computer Society Press, Los Alamitos, CA, 436-441.

FEO, T. AND RESENDE, M. 1995. Greedy randomized adaptive search procedures. J. Global Optim. 6, 109-133.

GAVRIL, F. 1973. Algorithms for a maximum clique and a maximum independent set of a circle graph. Networks 3, 261-273.

GOLDSCHMIDT, O. AND TAKVORIAN, A. 1994. An efficient graph planarization two-phase heuristic. Networks 24, 69-73.

GOLUMBIC, M. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, Inc., New York, NY.

HOPCROFT, J. AND TARJAN, R. 1974. Efficient planarity testing. J. ACM 21, 4 (Oct.), 549-568.

JAYAKUMAR, R., THULASIRAMAN, K., AND SWAMI, N. 1989. O([n.sup.2]) algorithms for graph planarization. IEEE Trans. Comput.-Aided Des. 8, 257-267.

JUNGER, M. AND MUTZEL, P. 1996. Maximum planar subgraphs and nice embeddings: Practical layout tools. Algorithmica 16, 33-59.

LEMPEL, A., EVEN, S., AND CEDARBAUM, I. 1966. An algorithm for planarity testing of graphs. In Proceedings of the International Symposium on Theory of Graphs (Rome) Gordon and Breach Science Publishers, Inc., Langhorn, PA, 215-232.

LIU, P. AND GELDMACHER, R. 1977. On the deletion of nonplanar edges of a graph. In Proceedings of the 10th Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL) 727-738.

RESENDE, M. G. C. AND RIBEIRO, C. C. 1997. A GRASP for graph planarization. Networks 29, 173-189.

SARRAFZADEH, M. AND LEE, D. 1989. A new approach to topological via minimization. IEEE Trans. Comput.-Aided Des. 8, 890-900.

TAKEFUJI, Y. AND LEE, K. 1989. A near-optimum parallel planarization algorithm. Science 245, 1221-1223.

Received: September 1997; revised: March 1999; accepted: May 1999

CELSO C. RIBEIRO Catholic University of Rio de Janeiro and MAURICIO G. C. RESENDE AT&T Labs Research

Authors' addresses: C. C. Ribeiro, Department of Computer Science, Catholic University of Rio de Janeiro, Rio de Janeiro, RJ 22453-900, Brazil; email: celso@inf.puc-rio.br; M. G. C. Resende, Information Sciences Research Center, AT&T Labs Research, Room C241, 180 Park Avenue, Florham Park, NJ 07932; email: mgcr@Wresearch.att.com. Permission to make digital/hard copy of part or all of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial advantage, the copyright notice, the title of the publication, and its date appear, and notice is given that copying is by permission of the ACM, Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.

Printer friendly Cite/link Email Feedback | |

Author: | RIBEIRO, CELSO C.; RESENDE, MAURICIO G. C. |
---|---|

Publication: | ACM Transactions on Mathematical Software |

Article Type: | Statistical Data Included |

Geographic Code: | 3BRAZ |

Date: | Sep 1, 1999 |

Words: | 4594 |

Previous Article: | The RISC BLAS: A Blocked Implementation of Level 3 BLAS for RISC Processors. |

Next Article: | Algorithm 798: High-Dimensional Interpolation Using the Modified Shepard Method. |

Topics: |