# Modifying Orthogonal Drawings for Label Placement
## 4 Complexity Issues
Each edge \(i\) has \(m\)\(U\)-shape bends, as shown in Figure 5.  
Last, we assign a label to each of the \(3m\) edges we have inserted into the interior of the skeleton drawing. The label for edge \(i\) corresponds to the weight \(a_{i}\) of the three-partition instance; it has width \(a_{i}\) and height \(m\). In addition, we assign a label of height \(3m\) and width \(K\) to each of the \(m\) edges of the top horizontal side of the skeleton rectangle. To preserve the orthogonal representation and area of the orthogonal drawing \(\Gamma\), while modifying \(\Gamma\) in order to assign overlap-free edge labels, we can only slide horizontally and/or stretch vertically the \(U\)-shapes of the edges, since we cannot alter the skeleton drawing. Thus, we have the following:  
**Fact 1**. : _We can modify the drawing only by sliding horizontally and/or stretching the U-shapes of the interior edges without creating any crossings._  
Figure 4: The buckets of the orthogonal drawing. Figure 5: The interior edges of the skeleton drawing, one edge for each of the \(3m\) elements of an instance of the three-partition problem. Figure 3: The structure of the skeleton drawing. Note that the drawing is a grid drawing; thus, two objects that do not overlap are separated by at least one unit. Next, we will show that the orthogonal drawing \(\Gamma\) corresponding to an instance \(p\) of the three-partition has an overlap-free edge label assignment if and only if \(p\) has a solution. **Theorem 2**. : _The orthogonal drawing \(\Gamma\) that represents an instance \(p\) of a three-partition problem has an overlap-free edge label assignment if and only if \(p\) has a solution. \(\Gamma\) can be modified without increasing its area, while preserving its orthogonal representation, in order to find an overlap-free edge label assignment._  
Proof. : From the construction of the orthogonal drawing \(\Gamma\), it follows that the label of each edge of the top horizontal side of the skeleton drawing, in order to be overlap-free, has to stretch exactly one \(U\)-shape bend from each edge below, as shown in Figure 6 (we call such a multilayer \(U\)-shape a _super_\(U\)-shape). Each super \(U\)-shape \(u\) has height \(6m\); thus, \(u\) must be inside some bucket in order to avoid overlaps, since the height of \(\Gamma\) is \(6m+1\). Each super \(U\)-shape \(u\) has width \(6m+K\). By construction, each bucket has width \(6m+B+K+2\) from which \(6m+K\) units are occupied by \(u\) and two units are used to separate the two vertical edges that define the boundaries of each bucket. Hence, there will be \(B\) free units of width in each bucket. This implies that at most one label of a top horizontal edge can be placed inside a super \(U\)-shape, since each label of a top horizontal edge has width \(K\) and \(K>B\). The label of each interior edge \(i\) must be placed inside some bucket, since this is the only way to avoid overlaps; see Figure 7. Then, the width of a super \(U\)-shape will increase by \(a_{i}\). By construction, there will be \(B\) free units of width in each bucket. Thus, a three-set of labels \(i\), \(j\) and \(k\) fit exactly into a bucket if and only if the sum of \(a_{i}\), \(a_{j}\) and \(a_{k}\) is equal to \(B\). Note that by definition \(B/4<a_{i}<B/2\), for each \(i\), which implies that in each bucket, there can be at most three overlap-free labels, and because there are \(m\) buckets, it is trivial to conclude that each bucket must contain exactly three labels in order to have all labels free of overlaps. This implies that each label can fit into some bucket if and only if the weight of each set of three labels in each bucket is equal to \(B\), which proves the theorem. Figure 6: The labels of the top horizontal edges and the \(U\)-shape bends of the edges below that stretch. Figure 2:0 A simple example of an orthogonal drawing corresponding to an instance of the three-partition problem with \(m=2\), \(K=8\), \(B=7\) and weights \(2,2,2,2,3,3\).