# Modifying Orthogonal Drawings for Label Placement
## 6 Polynomial Time Algorithms for the One-Dimensional Separation Problem
### The Flow Method  
In this section, we use minimum flow techniques to find the minimum width needed to eliminate label overlaps in an orthogonal drawing \(\Gamma\), given a partial order of overlapping objects, while preserving the orthogonal representation of \(\Gamma\). The case of finding minimum height is analogous. Generally speaking, we will create a directed acyclic graph \(G_{flow}\) that transfers flow from the top to the bottom of the drawing in order to insert extra vertical space to resolve horizontal overlaps. Intuitively, if two objects overlap, then we must push between them at least as much flow as the amount of their overlap in the \(x\)-direction. We create a digraph that captures all possible routes that we can push flow such that all horizontal overlaps are resolved. Since we want to preserve the orthogonal representation of the drawing, we insert space in such a way that the path of the inserted space does not intersect any vertical edge segment. It is important to note that the space opened at the top of the drawing can be reused by objects below, and the goal is to maximize the reuse of the space. First, we decompose the input drawing into vertical edge segments, nodes and labels. Next, we remove all horizontal edge segments. Then, we group nodes and edge segments that are connected and share the same column in the drawing into single vertical objects, in order to preserve the orthogonal representation of the drawing. Next, we obtain the partial order of the objects (vertical objects, nodes and labels) in the decomposed drawing. Then, we create a special graph, which we call the _separation visibility_ graph \(G_{sp}\). We will use a plane sweep method similar to the one described in the previous section to find the partial order of the objects. We sweep the plane from left to right, and each time, we encounter an object for the first time we place it at the end of a queue. The order in which we have placed each object in the queue reveals its position in the partial order. Note that a label to the right of its associated vertical edge goes after the edge into the queue. Then, we construct the separation visibility graph \(G_{sp}\) as follows: For each vertical segment and node of the decomposed input drawing, we insert a node in \(G_{sp}\). For each edge label \(l\), which is a rectangle, we insert two nodes and two horizontal edges in \(G_{sp}\). The nodes correspond to the vertical sides of \(l\) and the edges to the horizontal sides of \(l\). Next, we insert edges in \(G_{sp}\) by expanding (to the left and to the right) the horizontal sides of each node in \(G_{sp}\) until they touch another node of \(G_{sp}\). Figure 19a illustrates the ordered set of objects corresponding to the input drawing with overlapping labels shown in Figure 13a. The corresponding separation visibility graph is shown in Figure 19b. Notice that we add two vertical line segments (nodes in \(G_{sp}\)), one to the left and one to the right of the set of ordered objects. By adding these two objects, we ensure that each face of the separation visibility graph is a rectangle. **Fact 2**. : _Each face of the separation visibility graph is a rectangle._  
We assign a weight to each edge \(e\) of \(G_{sv}\), which represents the minimum distance the two objects connected with edge \(e\) must be kept apart to avoid overlaps. We assign weights in the following fashion:  
* Each edge that connects two overlapping objects has weight equal to the amount of overlapping between these objects in the \(x\)-direction plus one. * Each edge that corresponds to a horizontal side of a rectangle that represents either a label or a node has weight equal to the width of that label or node. * Each edge that connects an edge \(e\) of the original drawing to a label assigned to \(e\) has weight zero. * Any other edge has weight one. Next, we show how to create the graph \(G_{flow}\) from the separation visibility graph \(G_{sv}\) (see Figure 20):  
* Insert into \(G_{flow}\) nodes \(s\) and \(t\) above and below, respectively, of \(G_{sv}\).