# Modifying Orthogonal Drawings for Label Placement
## 5 Heuristics for the OSLP Problem
### Resolving Overlaps  
Given an orthogonal drawing \(\Gamma\) with labels assigned to each edge of \(\Gamma\), we resolve label overlaps by increasing the height and/or width of \(\Gamma\) while preserving its orthogonal representation. From Section 4, where we present complexity results for the OSLP problem, it is clear that heuristics must be used to insert space to resolve overlaps for the OSLP problem.  
Generally speaking, we will use a two-phase technique to resolve overlaps. During Phase 1, we resolve overlaps in the \(x\)-direction. Analogously, in Phase 2, we resolve overlaps in the \(y\)-direction. First, we define a partial order of all graphical features in the drawing (nodes, edges and labels). Next, we use plane sweep and flow techniques to find the minimum width and/or height needed to push apart objects in the drawing, so that all label overlaps are eliminated.  
The OSLP problem has many similarities with the compaction problem in VLSI layout [16; 17]. In both problems, the objective is to fit into the smallest area a set of geometric objects subject to a given set of constraints. The VLSI compaction problem is NP-complete, even if we allow objects to move only in one direction to resolve overlaps [16]. Actually, [PERSON] [17] has pointed out that what makes the compaction problem computationally hard is that it is difficult to decide the partial order of two objects that overlap. We believe that this is what makes the OSLP problem hard, as well. Once a partial order for all objects is given, the compaction problem is solved in polynomial time if in addition objects are allowed to move only in one direction [16].  
Next, we will show that the same holds true for the OSLP problem, as well. If the partial order of overlapping objects is given and labels in the drawing are allowed to move only in one direction (horizontal or vertical), then we can find the minimum area needed to resolve overlaps in polynomial time, while preserving the orthogonal representation of the input drawing. We will refer to it as the _one-dimensional separation_ problem.  
**The one-dimensional separation problem:**  
**Instance:** A drawing \(\Gamma\) with a label assignment with overlaps.  
**Question:** Increase the width (height) of \(\Gamma\) minimally, so that all overlaps in the \(x\)- (\(y\)-) direction are eliminated, while preserving: (i) the \(y\)- (\(x\)-) coordinates of all labels; (ii) the partial order of all the objects in \(\Gamma\); (iii) the orthogonal representation of \(\Gamma\).  
We note the partial order of two objects \(i\) and \(j\) as \(i\prec j\) when object \(i\) is to the left (respectively bottom) of \(j\). In the one-dimensional separation problem, we do not allow parts of the drawing to be swapped in order to preserve the partial order, and we do not allow insertions of new bends or crossings in order to preserve the orthogonal representation. Generally speaking, the only action that is allowed is stretching the edges in the drawing such that we allocate space that allows overlapping labels to separate.  
Next, we present two polynomial time algorithms for solving the one-dimensional separation problem. We will present the case where we increase only the width of the drawing to remove overlaps; the case of increasing the height is analogous.