Single bend wiring on surfaces

Discrete Applied Mathematics 117 (2002) 27–40 Single bend wiring on surfaces M.A. Garridoa;∗;1,A.M#arqueza;1, A. Morganab, J.R. Portilloa;1 aDept. Matem atica Aplicada I, Universidad de Sevilla, Avda. Reina Mercedes s=n, 41012-Sevilla, Spain bDept. Matematica, Universit a di Roma “La Sapienza”, Roma, Italy Received 7 July 1998; received in revised form 9 November 2000; accepted 2 January 2001 Abstract The following problem of rectilinear routing is studied: given pairs of points on a surface and a set of permissible orthogonal paths joining them, whether is it possible to choose a path for each pair avoiding all intersections. We prove that if each pair has one or two possible paths to join it, then the problem is solvable in quadratic time, and otherwise it is NP-complete. From that result, we will obtain that the problem of 5nding a surface of minimum genus on which the wires can be laid out with only one bend is NP-hard. ?2002 Elsevier Science B.V. All rights reserved. Keywords: VLSI design; Connection; Bend wiring; Surface 1. Introduction Orthogonal layouts are used in many applications of computer science as circuit schematics, data =ow diagrams in Software Engineering or entity relationships diagrams [1,2]. This fact has attracted the attention of many authors and numerous results have been obtained about orthogonal drawings [3,6,9–12]. The problem of connecting pairs of points on the plane using orthogonal paths with at most one bend was studied by Raghavan et al. [11]. A pair of points to be connected is called a wire. They develop an O(m2) algorithm to determine whether or not a set of mpoint pairs can be wired in this manner on the plane. The paths are not allowed to cross, hence most wire sets cannot be wired in a rectilinear fashion on the plane. In this case, the authors proved that the problem of determining a maximum cardinality subset of wires which can be laid out in a single bend fashion on the plane is NP-hard. ∗Corresponding author. E-mail addresses: [email protected] (M.A. Garrido), [email protected] (A. M#arquez), [email protected] (A. Morgana), [email protected] (J.R. Portillo). 1Partially supported by dgicyt project PB96-1374 and PAI project FQM-0164. 0166-218X/02/$ - see front matter ?2002 Elsevier Science B.V. All rights reserved. PII: S0166-218X(01)00177-9 28 M.A. Garrido et al. / Discrete Applied Mathematics 117 (2002) 27–40 In order to extend the results of [11] to realistic constrains on circuit routing, some other works have appeared [4,7]. In many applications, the connections are constructed using more than one layout. This fact together with the results about the plane lead to the problem on other surfaces. Observe that, as it is pointed out in [8] layout problem is a multiobjective optimization problem, and there are many cost functions that are of interest in layout. Among those functions we can cite two: via count and the maximum number of bends per wire. A via is a change of layer in a wire and usually introduces electrical instabilities that decrease the yield, additionally, the use of vias increase the diIculties of some manufacturing process. And a bend in a wire has adverse eJects on the delay and other electrical properties of the wire. Although, vias and bends are related, in general they do not need to be correlated. To allow only one bend for each wire has in addition some extra advantages on other cost functions, since wires with only one bend have always minimum length and all wires are represented in a minimum area. But, in this case, vias are unavoidable. In some sense, we address here the problem of minimizing vias in the following way, each time that two wires intersect, we can avoid that intersection by introducing a via. As far as a via introduces a hole in a printed board that presents typically two faces we can model our problem as a single bend wiring on a surface, of course to minimize the number of vias is equivalent to asking for the problem of minimizing the genus of the surface where we are representing our pairs of points. And we will prove that this is a NP-hard problem. This paper is structured in the following way. In the next section, we will model in an adequate way our problem. Then, we will prove in the third section that if we use only two path between each pair of points, then the problem is solvable in polynomial time. The fourth section is devoted to the general problem, and we include a section with some concluding remarks and open problems. 2. Modeling single bend wiring on surfaces First of all, an adequate representation of a surface of genus gis needed to connect pairs of points orthogonal paths, namely, a system of orthogonal lines must be de5ned on the surface. The planar representation of the surface of genus 1 (the torus) is a rectangle whose parallel sides are identi5ed. This rectangle will be the external rectangle of the standard orthogonal surfaces that are constructed as follows: The standard orthogonal surface of genus g[6] is obtained by the deletion of g−1 small rectangles or windows in the interior of the external rectangle (diJerent positions for the same number of windows lead to homeomorphic surfaces). The sides of all rectangles (external rectangle and windows) are parallel and the opposite sides of each window are also identi5ed. In this way, two distinguished directions are de5ned, the horizontal (= direction of the parallels) and the vertical direction (= direction of the meridians), respectively. Note that these directions are parallel to the sides of the external rectangle M.A. Garrido et al. / Discrete Applied Mathematics 117 (2002) 27–40 29 Fig. 1. The standard orthogonal surface of genus gand its orthogonal system. Fig. 2. The eight possible single bend wirings on a surface of genus g. (see Fig. 1). Hence, in order to obtain such a representation of a surface it is necessary to 5x one parallel and one meridian forming the sides of the external rectangle. They are called external parallel and meridian. We can 5x a coordinate system in which the axes are the external parallel and meridian, x- and y-axis respectively, and the origin is the point in the bottom left-hand corner of the standard orthogonal surface. In this way, any point or window on the surface may be speci5ed by its x- and y-coordinates. Notice that a surface is de5ned by the number and positions of its windows. An orthogonal path is made up of horizontal and vertical segments. These paths are called rectilinear wirings or layouts. The number of bends of each rectilinear path can be diJerent, but, as we mentioned in the Introduction, from a practical point of view, there are many applications where it is necessary to limit to one the number of them on each rectilinear connection. When the wiring is restricted such that no wire has more than one bend, it is called a single bend wiring. Given a pair of points on the plane, there are at most two ways to wire them using only one bend, lower and upper wirings (see Fig. 2 (0;0;0) and (0;0;1)); Fig. 2(0;∗;∗) corresponds to the possible single bend wirings for two points on the cylinder. In general, there are at most eight wirings connecting a wire on a surface of genus g¿1 using only one bend (Fig. 2). But, it is very common to face situations where no all possible wirings are permitted, typically by the situation of some components that obstruct those wirings. 30 M.A. Garrido et al. / Discrete Applied Mathematics 117 (2002) 27–40 Each single bend wiring is identi5ed by three Boolean variables (vc; hc; d)inthe following way: The variables vc and hc indicate the possible intersection between the rectilinear layout and the external parallel and meridian respectively. Set vc (hc) to true if and only if the single bend wiring intersects with the external parallel (meridian). For each single bend wiring, the variable dindicates if the segment adjacent to the upper point wire is horizontal or vertical. Set dto true if and only if this segment is horizontal. Fig. 2 shows the eight possible wirings and the corresponding values of the variables. The single bend layouts with vc or hc being true are called essential wirings. Below, we pose the general problem studied in this article, distinguishing whether the connections are forced to be constructed along 5xed layouts or all the wirings are permitted. Single bend wiring on surfaces with xed layouts (n-SBWS): Instance: Surface S, a wire set Won Sand at most npossible single bend wirings for each wire. Question: Can Wbe single bend wired on Susing the given wirings and without intersection between the layouts of diJerent wires? For the sake of simplicity, a wire with npossible single bend wirings will be called an n-wire. Single bend wiring on surfaces (SBWS): Instance: Surface Sand a wire set Won S. Question: Can Wbe single bend wired on Swithout intersection between the layouts of diJerent wires? As the maximum number of single bend wirings on any surface is eight, for the SBWS problem, each wire can be single bend wired using, exactly eight diJerent layouts. In Section 3, we show that the problem 2-SBWS can be solved eIciently for arbitrary surfaces. The algorithm has time complexity O(m2), where mis the number of wires in the instance. In Section 4, we prove that the n-SBWS problem for n¿3 is NP-complete for arbitrary surfaces. Too, the NP-completeness of the SBWS problem is established and, hence, 5nding a surface of minimum genus on which a given wire set can be single bend wired is NP-hard. 3. Feasibility of 2-SBWS In this section, we outline how to determine in polynomial time whether or not a given 2-wire set Won a surface Sof genus gcan be single bend wired feasibly (i.e., without intersections). Raghavan et al. [11] solved this problem on a plane layer, where at most two possible single bend wirings for each wire exist. On surfaces of higher genus, the number of possible layouts is increased. On the cylinder there are at most four possible layouts and on the torus and surfaces of higher genus there are at most eight layouts for each wire. In these cases, there are more than a single possibility for choosing the two allowed layouts. The inspection of the intersection of layouts on the plane considered in [11] can be applied only in few cases and new cases appear. M.A. Garrido et al. / Discrete Applied Mathematics 117 (2002) 27–40 31 Fig. 3. A wire on the torus with two pre5xed layouts and the assignment of truth values for each layout. We consider all m(m−1)=2 pairs of wires in W;where mis the cardinality of W. For each pair we have three options: (a) The two wires cannot be laid out feasibly. Then, the wire set Wcannot be single bend wired feasibly on the surface S. If this case occurs for a pair, the answer for the 2-SBWS given instance is no. (b) There are no intersections between layouts of two wires. (c) There are intersections between some layouts of both wires but there are one or more feasible combinations of layouts. The information of a 2-SBWS instance can be shown as a Krom formula which is satis5able if and only if the corresponding wire set can be laid out (without intersection) in single bend fashion. A Krom formula (or 2-CNF formula) is a Boolean expression which is in conjunctive normal form (CNF) and contains at most two literals per clause. The codi5cation process in a logic formula is done as follows: we associate a Boolean variable uito each wire wiin W. The truth value assigned to the variable corresponds to the layout of the wire, say true for the layout with smallest label (in the lexicographic ordering) (vc; hc; d), now called the lower layout, and false for the layout with biggest label (the higher layout). An example is shown in Fig. 3. vc,hc and dare the variables associated to the layout, as described in the introduction (see Fig. 2). Note that this assignment is compatible with the assignment done for the plane in [11] and, in this case, the words higher and lower refer to the geometrical location of the layouts. Each interaction between two wires can be turned into a Boolean formula inspecting the possible crossings between layouts. There are sixteen classes of interaction: (1) ui∧N ui. Infeasibility. This corresponds to case (a) mentioned above. (2) ui∨N ui. No intersections. This corresponds to case (b) mentioned above. (3) ui. The lower layout for widoes not cross any layout from wj, but the higher layout for wiis infeasible. (4) uj. Symmetric to case (3) when iis replaced by j. (5) N ui. Symmetric to case (3) when the lower layout is replaced by the higher layout. (6) N uj. Symmetric to case (4) when the lower layout is replaced by the higher layout. (7) ui∨N uj. The lower layout for widoes not intersect any layout of wj, and the higher layout for wjdoes not cross any layout of wi. The higher layout of wiand the lower layout of wjcan be laid out simultaneously. 32 M.A. Garrido et al. / Discrete Applied Mathematics 117 (2002) 27–40 Fig. 4. All possible classes of interaction up to symmetries. The discontinuous lines correspond to the index j. (8) N ui∨uj. Symmetric to case (7) when iis replaced by j. (9) (ui∨uj)∧(N ui∨N uj). Two possible connections. The higher layout for one of the two wires and the lower layout for the other one. (10) ui∧N uj. Only the lower layout for wiand the higher layout for wjare feasible simultaneously. (11) N ui∧uj. Symmetric to case (10) when iis replaced by j. (12) ui∨uj. The lower layouts are both feasible and there are intersection between the higher layouts. (13) N ui∨N uj. The higher layouts are both feasible and there are intersection between the lower layouts. (14) ui∧uj. Only the lower layouts are feasible simultaneously. (15) N ui∧N uj. Only the higher layouts are feasible simultaneously. (16) (ui∨N uj)∧(N ui∨uj). In this case there are two possibilities. Either both wires have to be laid out using the higher layout or using both the lower layout. Note that classes (1)–(9) of interactions can appear on the plane [11] and (1)–(16) can appear on the cylinder and on surfaces of higher genus. Note also that these sixteen clauses are all possible Boolean 2-clauses with at most two variables (Fig. 4). Each pair of points can be connected using eight possible single bend wirings on a surface of genus g(Fig. 2). Then, we have 28 possible choices of two layouts for each 2-wire. Two pairs of points can be placed in 72 diJerent relative positions, up to vertical symmetries between the pairs. Thus, there are 56 448 (28 ×28 ×72) diJerent pairs of 2-wires. Using a simple computer routine, all the 56 448 diJerent pairs of wires on a surface of arbitrary genus have been turned into Boolean formulae. Note that a same pair can produce diJerent clauses on diJerent surfaces (see Fig. 5). M.A. Garrido et al. / Discrete Applied Mathematics 117 (2002) 27–40 33 Fig. 5. DiJerent clauses for the same wiring on diJerent surfaces. When all the interactions are turned into Boolean formulae, the result is a Krom formula with at most two clauses in each relation. Theorem 1. The 2-SBWS problem is solvable in quadratic time. Proof. The m(m−1)=2 interaction relations between pairs of 2-wires determine the same number of Boolean formulae which must be satis5ed simultaneously. Then, the conjunction of all these formulae corresponds to the entire set of pairs of 2-wires. Obviously, it is possible to exclude those formulae corresponding to case (2), because they are tautologies. This gives a Krom formula containing at most O(m2) clauses. One can determine whether a Krom formula is satis5able in linear time in the number of clauses and 5nd within the same asymptotic time a satisfying truth assignment if one exists [5]. Hence, in our case it can be decided in O(m2) time whether there exists a satisfying truth assignment and in the aIrmative case such an assignment can be found in O(m2) time. If a satisfying truth assignment can be found, it is a simple task to construct the equivalent wire layout for the wire set W. 4. Single bend wires on surfaces of minimum genus Given a wire set, Raghavan et al. [11] developed an O(m2) algorithm to determine whether or not a set of mwires can be single bend wired on a plane layer. For those wire sets that cannot be single bend wired on the plane, the question of determining a maximum cardinality subset such that all their wires can be laid out in single bend fashion on the plane is considered. These authors established the NP-hardness of this second problem. Another option for such wire sets could be to introduce vias or layouts on surfaces of higher genus. As we have indicated in the introduction, there are at most two ways to wire a pair of points on the plane using only one bend. On an arbitrary surface, for a wire there are eight possible single bend layouts. 34 M.A. Garrido et al. / Discrete Applied Mathematics 117 (2002) 27–40 Fig. 6. (a) Clause assembly , (b) variable wire !. In the previous section, we have seen that it is possible to solve in polynomial time single bend wiring on surfaces when only two layouts for each wire are permitted (2-wires). Now, we will observe that the situation changes drastically if three or more wiring are permitted for each wire. In this section, we prove the completeness of two problems: n-SBWS for n¿3 and SBWS. Note that the result for one problem is not an immediate consequence of the other one because, for each wire there are at most npossible wirings for the n-SBWS problem and exactly eight wirings for the SBWS problem. Observe that an optimization problem related with SBWS is to 5nd a surface of minimum genus on which the wires can be laid out with only one bend. Obviously, if we can give an answer to this problem in polynomial time, we will know to solve the SBWS problem in polynomial time. Hence, the problem of determining the minimum genus of a surface on which a wire set can be laid out in single bend fashion is NP-hard. Theorem 2. The 3-SBWS problem is NP-complete. Proof. 3-SBWS is readily seen to be solvable in nondeterministic polynomial time, i.e., 3-SBWS is in NP. Thus, in order to prove the NP-completeness of the problem 3-SBWS,it suIces to transform an NP-complete problem to ours. In order to do this we consider the well-known NP-complete problem 3-SATISFIABILITY (3-SAT). Let U={u1;u 2;:::;u p} be a set of variables and let C={c1;c 2;:::;c q}be a set of clauses making up an arbitrary instance Rof 3-SAT. Corresponding to R, we construct a 3-SBWS instance T as follows: Step 1. Each clause ciwill be represented by a clause assembly i, shown in Fig. 6(a) (for each wire, only the permitted layouts are pictured). The three literals of each clause are indexed following the enumeration of its corresponding variables (it can be supposed no clause contains the same complemented and non-complemented variable). With this order, let ll i,lm iand lh ibe the lowest, medium and highest index literals of the clause ci, respectively. The literal wires l i,m iand h iof the clause assembly iare associated to ll i,lm iand lh i, respectively. M.A. Garrido et al. / Discrete Applied Mathematics 117 (2002) 27–40 35 Fig. 7. Variable wire !iand literal wires i. Place the clause assemblies 1;:::; qfrom top to bottom of the surface such that •if i¡j then the literal wires l i,m iand h iare on the left of l j,m jand h j; •there is no any meridian intersecting literal wires of diJerent clauses. The position of the lowest points of l,mand hwill be determined in Step 3. For each clause in R, the genus of the surface of Tis increased 6 units. Step 2. Each variable uiwill be represented by a variable wire !i, shown in Fig. 6(b). Let !u iand !l ibe the upper and lower points of the variable wire, respectively. Place the variable wires !1;:::;! punder the clause assemblies, from !1 to !p, such that •wu iis on the left of h 1and wl iis on the right of h q, where i=1;:::;p; •!iand !j(i=j) do not intersect. Step 3. Finally, we 5x the position of the lowest points of the literal wires as shown in Fig. 7. The diJerent situations depend on the type of literal wire, i.e., l,mor h, and whether or not the corresponding literal is a complemented one. In any case, the lowest points of the literal wires are placed under their respective variable wires. The genus of the surface is increased 2 units for each literal wire to place, hence 6qunits. In order to place these wires as Fig. 7 determines, the genus of the surface is increased to avoid intersections between literal wires and the posterior clauses assemblies and anterior variables wires. If literal libelongs to the clause cjthen the genus of the surface, that is 12q+ 1, is increased 2(q−j) units to avoid intersections between i and the clause assemblies j+1;:::; q. In addition, it is necessary to add 4(i−1) units corresponding to !1;:::;! i−1. This completes the construction of the 3-SBWS instance Tcorresponding to R. It is easily veri5ed that the genus of the surface Sand the number of wires in T constructed is polynomial in pand q.