How can we reconfigure a given set of n segments with fixed endpoints in the plane into a crossing-free set? We remove a pair of crossing segments and insert one of the two pairs of non-crossing segments with the same four endpoints in an operation called a flip. If we restrict ourselves to sets of segments with a given property, say forming one polygon, the inserted pair must preserve this property. Untangling a set of segments amounts to iteratively flip the set of segments until no crossing remains.

Why are flips useful? A flip shortens the total length of the segments. Hence, to efficiently compute approximations of the shortest tour through n given cities, many well known algorithms are supplemented with flips.

How many flips are needed? At most n3 flips may be performed in a sequence, but the longest sequence known uses only roughly n2 flips. In general, no strategy for choosing which pairs of crossing segments to remove is known to untangle a set of segments using fewer than n3 flips. Yet, when the endpoints form a convex polygon, the problem is well understood: the longest sequences use roughly n2 flips, while the best strategies use roughly n flips.

In this dissertation, we devise strategies to untangle segments for several versions of flips: the flips with nothing to preserve (the segments form a multigraph or a matching), the flips preserving a bipartite matching, the flips preserving a polygon (i.e., a tour), and the flips preserving a tree. We study the performance of each strategy in terms of their number of flips. Our results are organized by the type of choice the strategy uses, as follows. We first study the performance of the strategy choosing nothing, i.e., we improve the bounds on the number of flips in the longest flip sequences (in special cases). We then devise strategies for choosing which pairs of segments to remove to untangle segments using as few flips as possible. We also devise strategies for choosing which pairs of segments to insert, and strategies for choosing both removed and inserted pairs. Many of our results use a parameter measuring how far from a convex polygon the set of endpoints is. Furthermore, we prove the NP-hardness of the shortest flip sequence to untangle a bipartite matching.