# Modifying Orthogonal Drawings for Label Placement
## 6 Polynomial Time Algorithms for the One-Dimensional Separation Problem
### The Flow Method
* Insert into \(G_{flow}\) a node for each face of \(G_{sv}\). * Add edges into \(G_{flow}\) that connect two neighboring faces of \(G_{sv}\) that share a horizontal edge segment. Edges are directed towards the face with a smaller \(y\)-coordinate. * Connect with edges node \(s\) to each face that has a horizontal segment visible from a horizontal line that intersects node \(s\). * Connect with edges each face that has a horizontal segment visible from a horizontal line that intersects node \(t\) to node \(t\). Figure 19: (**a**) Ordered vertical objects; (**b**) their separation visibility graph. By the construction of the separation visibility graph and Fact 2 we can prove the following result:  
**Lemma 1**. : _Graph \(G_{flow}\) includes every possible path that can be used to open up space in the \(x\)-direction to resolve overlaps without changing the orthogonal representation of the input orthogonal drawing._  
In order to find the minimum width needed to resolve overlaps, we assign a lower and upper capacity to each edge of \(G_{flow}\). Notice that each edge in \(G_{flow}\) intersects an edge in the corresponding \(G_{sv}\) graph. Each edge in \(G_{flow}\) has lower and upper capacity equal to a pair of weights for the only edge in \(G_{sv}\) that intersects. We obtain the pair of weights for each edge in \(G_{flow}\) as follows:  
* Each edge that connects two overlapping objects has lower weight equal to the amount of overlapping between these objects in the \(x\)-direction plus one. * Each edge that connects an edge \(e\) of the original drawing to a label assigned to \(e\) has upper and lower weight zero. * Each remaining edge, other than edges connecting two vertical sides of labels, has lower weight one. * Each edge connecting the two vertical sides of a label has upper and lower weight equal to the width of the label. * Each edge, other than those connecting two vertical sides of a label or each edge \(e\) of the original drawing to a label assigned to \(e\) has upper weight equal to \(+\infty\). Next, we show that the minimum flow of \(G_{flow}\) produces the minimum width expansion needed to resolve overlaps. **Theorem 4**. : _The minimum flow of \(G_{flow}\) gives the minimum width of the drawing, such that all overlaps are resolved in one direction, and the orthogonal representation of the drawing is preserved._  
Proof. : The resulting drawing has the same orthogonal representation since we do not allow flow to cross vertical edges of the drawing. By construction, for any pair of overlapping labels, there will be enough flow going through to push them apart; thus, the resulting drawing has no overlaps. Let us assume that the minimum flow of \(G_{flow}\) does not produce minimum width. This means that we have inserted extra vertical space. Therefore, there exists a path in \(G_{flow}\) from source to sink that carries at least one unit of extra flow. This is a contradiction, since we have obtained a minimum flow for \(G_{flow}\). Sophisticated techniques can solve the minimum flow problem in \(O(m\ log\ n\ (m\ +\ n\ log\ n))\) time [19; 20], where \(n\) is the number of vertices and \(m\) is the number of edges of \(G_{flow}\). The coordinates  
Figure 20: The flow graph of the separation visibility graph shown in Figure 19b. of the resulting orthogonal drawing can be easily obtained, since the flow in each edge of \(G_{flow}\) gives the offset of objects in the original drawing that the corresponding edge in the visibility graph connects.