# Modifying Orthogonal Drawings for Label Placement
## 4 Complexity Issues  
First, we consider the more general case of the OSLP problem: Given an orthogonal drawing, increase its area minimally to achieve an overlap-free edge label assignment. This problem is NP-hard,  
Figure 1: Three orthogonal drawings of the same graph. Drawings (**a,b**) have the same orthogonal representation, while a drawing of a different orthogonal representation is shown in (**c**). Figure 2: (**a**) An orthogonal drawing with overlapping edge labels; (**b**) edge label overlaps have been resolved by inserting extra space using our flow technique. which results from the fact that the problem of assigning labels to edges of a graph drawing, without increasing the area of the drawing, is NP-hard [12]. Hence, we have the following theorem:  
Theorem 1: _The OSLP problem is NP-hard._  
Next, we consider the following variation of the OSLP problem:  
**The Restricted Opening Space Label Placement (ROSLP) problem: Instance:** Given an orthogonal drawing with a label associated with each edge of the drawing. **Question:** Is there a label assignment where each edge has an overlap-free label assigned to it without increasing the area of the drawing, while preserving its orthogonal representation? In the ROSLP problem, the goal is to reroute the edges of the orthogonal drawing in order to assign overlap-free labels. In addition, we must not increase the area of the drawing, and we have to preserve the orthogonal representation of the drawing. Next, we prove that the ROSLP problem is NP-complete. _The NP-Completeness of the ROSLP Problem_  
We will prove that the ROSLP problem is NP-complete by transforming the three-partition problem [13], a well-known NP-complete problem, into it. Recall that the three-partition problem is defined as follows:  
**The three-partition problem: Instance: \(3m\) weights \(a_{i}\in Z^{+}\), a bound \(B\in Z^{+}\), such that \(B/4<a_{i}<B/2\) for each \(i\) and such that \(\sum_{i=1}^{3m}a_{i}=mB\). Question:** Can the set \(\{1,2,...,3m\}\) be partitioned into \(m\) disjoint sets \(A_{1}\), \(A_{2}\),..., \(A_{m}\), such that \(\sum_{a_{i}\in A_{j}}a_{i}=B\) for all \(A_{j}\)? Note that each \(A_{j}\) must contain exactly three elements. In order to transform the three-partition problem into ROSLP, we do the following: We construct an orthogonal drawing \(\Gamma\) with edge labels that corresponds to the three-partition problem. The goal is to associate a solution of the three-partition instance with the existence of an overlap-free edge label assignment of \(\Gamma\), while preserving the orthogonal representation and without increasing the area of \(\Gamma\). Next, we give an outline of our transformation. Given an instance \(p\) of the three-partition problem, we create an orthogonal drawing with edge labels corresponding to instance \(p\) in the following way: First, we construct a rectangular shape orthogonal drawing, which we call the _skeleton_ drawing, as shown in Figure 3. There are \(6m+2\) nodes on each vertical side, \(m+1\) nodes on the top horizontal side and \(m(6m+K+B+2)+1\) nodes on the bottom horizontal side, where \(K>B\). Note that we cannot change the orthogonal representation and must preserve the area of the drawing; thus, the bounding rectangle of the skeleton drawing must not change. Next, we partition the bottom side of the skeleton drawing into \(m\) buckets, one for each of the three-set \(A_{j}\) of a solution of the underlying instance \(p\) of the three-partition, by inserting \(m-1\) nodes and edges in the bottom side of the skeleton drawing, as shown in Figure 4. Each of these edges will have length \(3m\), and each bucket will have width \(6m+B+K+2\). Next, we insert \(3m\) edges into the skeleton drawing. Each edge connects nodes of the opposite vertical sides of the skeleton drawing with the same \(y\)-coordinates. The top most edge connects the two nodes of the highest \(y\)-coordinate that are not part of the top horizontal side of the skeleton rectangle. We proceed from top to bottom until a total of \(3m\) edges have been placed.