A string attractor of a string T[1..|T|] is a set of positions Γ of T such that any substring w of T has an occurrence that crosses a position in Γ, i.e., there is a position i such that w = T[i..i+|w|-1] and the intersection [i,i+|w|-1]∩ Γ is nonempty. The size of the smallest string attractor of Fibonacci words is known to be 2. We completely characterize the set of all smallest string attractors of Fibonacci words, and show a recursive formula describing the 2^{n-4} + 2^{⌈n/2⌉ - 2} distinct position pairs that are the smallest string attractors of the nth Fibonacci word for n ≥ 7. Similarly, the size of the smallest string attractor of period-doubling words is known to be 2. We also completely characterize the set of all smallest string attractors of period-doubling words, and show a formula describing the two distinct position pairs that are the smallest string attractors of the nth period-doubling word for n ≥ 2. Our results show that strings with the same smallest attractor size can have a drastically different number of distinct smallest attractors.

We study the problem of reconfiguring a crossing-free embedding of a graph on a surface, with edges represented as curves, into another crossing-free embedding of the same graph on the same surface with the same fixed vertex positions. In this process, we reroute one edge at a time while maintaining crossing-free intermediate embeddings. This problem was introduced by Ito et al. [TALG 2025], who showed that even if the graph is a matching of two edges, reconfiguration is not always possible in the plane, but is always possible on the torus. For matchings of two or more edges, they gave a necessary and sufficient condition for reconfigurable embeddings in the plane, but not on the torus. Our main result is that for matchings, trees and forests, reconfiguration is always possible on the torus, and consequently, on any orientable surface of genus at least one. In addition, we provide sufficient conditions for reconfiguration on orientable surfaces of genus at least one and in the projective plane. For more general graphs, we show that reconfiguration is not always possible.

Abstract. We prove that the computation of a combinatorial shortest path between two vertices of a graph associahedron, introduced by Carr and Devadoss, is NP-hard. This resolves an open problem raised by Cardinal. A graph associahedron is a generalization of the well-known associahedron. The associahedron is obtained as the graph associahedron of a path. Whether the combinatorial (i.e., graph-theoretic) distance between vertices of the associahedron can be computed in polynomial time is a tantalizing and important open problem, which is identical to the computation of the flip distance between two triangulations of a convex polygon, and the rotation distance between two rooted binary trees. Our result shows that an approach for this open problem is not promising if it is applicable to the generalized problem on graph associahedra. As a corollary of our theorem, we prove that the computation of a combinatorial shortest path between two vertices of a polymatroid base polytope cannot be done in polynomial time unless [Formula: see text]. Since a combinatorial shortest path on the matroid base polytope can be computed in polynomial time, our result reveals an unexpected contrast between matroids and polymatroids.

We study the electrical distribution network reconfiguration problem, defined as follows. We are given an undirected graph with a root vertex, demand at each non-root vertex, and resistance on each edge. Then, we want to find a spanning tree of the graph that specifies the routing of power from the root to each vertex so that all the demands are satisfied and the energy loss is minimized. This problem is known to be NP-hard in general. When restricted to grids with uniform resistance and the root located at a corner, Gupta, Khodabaksh, Mortagy and Nikolova [Mathematical Programming 2022] invented the so-called Min-Min algorithm whose approximation factor is theoretically guaranteed. Our contributions are twofold. First, we prove that the problem is NP-hard even for grids; this resolves the open problem posed by Gupta et al. Second, we give a refined analysis of the Min-Min algorithm and improve its approximation factor under the same setup. In the analysis, we formulate the problem of giving an upper bound for the approximation factor as a non-linear optimization problem that maximizes a convex function over a polytope.

The minimum sum coloring problem with bundles was introduced by Darbouy and Friggstad (SWAT 2024) as a common generalization of the minimum coloring problem and the minimum sum coloring problem. During their presentation, the following open problem was raised: whether the minimum sum coloring problem with bundles could be solved in polynomial time for trees. We answer their question in the negative by proving that the minimum sum coloring problem with bundles is NP-hard even for paths. We complement this hardness by providing algorithms of the following types. First, we provide a fixed-parameter algorithm for trees when the number of bundles is a parameter; this can be extended to graphs of bounded treewidth. Second, we provide a polynomial-time algorithm for trees when bundles form a partition of the vertex set and the difference between the number of vertices and the number of bundles is constant. Third, we provide a polynomial-time algorithm for trees when bundles form a partition of the vertex set and each bundle induces a connected subgraph. We further show that for bipartite graphs, the problem with weights is NP-hard even when the number of bundles is at least three, but is polynomial-time solvable when the number of bundles is at most two. The threshold shifts to three versus four for the problem without weights.

In this article, we consider a transformation of k disjoint paths in a graph. For a graph and a pair of k disjoint paths \(\mathcal{P}\) and \(\mathcal{Q}\) connecting the same set of terminal pairs, we aim to determine whether \(\mathcal{P}\) can be transformed to \(\mathcal{Q}\) by repeatedly replacing one path with another path so that the intermediates are also k disjoint paths. The problem is called Disjoint Paths Reconfiguration . We first show that Disjoint Paths Reconfiguration is \(\mathsf{PSPACE}\) -complete even when \(k=2\) . On the other hand, we prove that, when the graph is embedded on a plane and all paths in \(\mathcal{P}\) and \(\mathcal{Q}\) connect the boundaries of two faces, Disjoint Paths Reconfiguration can be solved in polynomial time. The algorithm is based on a topological characterization for rerouting curves on a plane using the algebraic intersection number. We also consider a transformation of disjoint s - t paths as a variant. We show that the disjoint s - t paths reconfiguration problem in planar graphs can be determined in polynomial time, while the problem is \(\mathsf{PSPACE}\) -complete in general.

The qubit routing problem, also known as the swap minimization problem, is a (classical) combinatorial optimization problem that arises in the design of compilers of quantum programs. We study the qubit routing problem from the viewpoint of theoretical computer science, while most of the existing studies investigated the practical aspects. We concentrate on the linear nearest neighbor (LNN) architectures of quantum computers, in which the graph topology is a path. Our results are three-fold. (1) We prove that the qubit routing problem is NP-hard. (2) We show that the qubit routing problem on a path can be solved in a fixed-parameter time where the number of two-qubit gates is a parameter. (3) We show that the qubit routing problem on a path can be solved in polynomial time if each qubit is involved in at most one two-qubit gate.

In this extended abstract, we describe CoRe Challenge 2022/2023, an international competition series aiming to construct the technical foundation of practical research for Combinatorial Reconfiguration. This competition series targets one of the most well-studied reconfiguration problems, called the independent set reconfiguration problem under the token jumping model, which asks a step-by-step transformation between two given independent sets in a graph. Theoretically, the problem is PSPACE-complete, which implies that there exist instances such that even a shortest transformation requires super-polynomial steps with respect to the input size under the assumption of $NP \neq PSPACE$. The competition series consists of four tracks: three tracks take two independent sets of a graph as input, and ask the existence of a transformation, a shortest transformation, a longest transformation between them; and the last track takes only a number of vertices as input, and asks for an instance of the specified number of vertices that needs a longer shortest transformation steps. We describe the background of the competition series and highlight the results of the solver and graph tracks.

In this paper, we consider a transformation of $k$ disjoint paths in a graph. For a graph and a pair of $k$ disjoint paths $\mathcal{P}$ and $\mathcal{Q}$ connecting the same set of terminal pairs, we aim to determine whether $\mathcal{P}$ can be transformed to $\mathcal{Q}$ by repeatedly replacing one path with another path so that the intermediates are also $k$ disjoint paths. The problem is called Disjoint Paths Reconfiguration. We first show that Disjoint Paths Reconfiguration is PSPACE-complete even when $k=2$. On the other hand, we prove that, when the graph is embedded on a plane and all paths in $\mathcal{P}$ and $\mathcal{Q}$ connect the boundaries of two faces, Disjoint Paths Reconfiguration can be solved in polynomial time. The algorithm is based on a topological characterization for rerouting curves on a plane using the algebraic intersection number. We also consider a transformation of disjoint $s$-$t$ paths as a variant. We show that the disjoint $s$-$t$ paths reconfiguration problem in planar graphs can be determined in polynomial time, while the problem is PSPACE-complete in general.

We study the problem of reconfiguring one minimum $s$-$t$-separator $A$ into another minimum $s$-$t$-separator $B$ in some $n$-vertex graph $G$ containing two non-adjacent vertices $s$ and $t$. We consider several variants of the problem as we focus on both the token sliding and token jumping models. Our first contribution is a polynomial-time algorithm that computes (if one exists) a minimum-length sequence of slides transforming $A$ into $B$. We additionally establish that the existence of a sequence of jumps (which need not be of minimum length) can be decided in polynomial time (by an algorithm that also outputs a witnessing sequence when one exists). In contrast, and somewhat surprisingly, we show that deciding if a sequence of at most $\ell$ jumps can transform $A$ into $B$ is an $\textsf{NP}$-complete problem. To complement this negative result, we investigate the parameterized complexity of what we believe to be the two most natural parameterized counterparts of the latter problem; in particular, we study the problem of computing a minimum-length sequence of jumps when parameterized by the size $k$ of the minimum \stseps and when parameterized by the number of jumps $\ell$. For the first parameterization, we show that the problem is fixed-parameter tractable, but does not admit a polynomial kernel unless $\textsf{NP} \subseteq \textsf{coNP/poly}$. We complete the picture by designing a kernel with $\mathcal{O}(\ell^2)$ vertices and edges for the length $\ell$ of the sequence as a parameter.

We initiate the study of k -edge-connected orientations of undirected graphs through edge flips for k ≥ 2. We prove that in every orientation of an undirected 2k -edge-connected graph, there exists a sequence of edges such that flipping their directions one by one does not decrease the edge connectivity, and the final orientation is k -edge connected. This yields an “edge-flip based” new proof of Nash-Williams’ theorem: A undirected graph G has a k -edge-connected orientation if and only if G is 2k -edge connected. As another consequence of the theorem, we prove that the edge-flip graph of k -edge-connected orientations of an undirected graph G is connected if G is (2k+2) -edge connected. This has been known to be true only when k=1 .

The total angular resolution of a straight-line drawing is the minimum angle between two edges of the drawing. It combines two properties contributing to the readability of a drawing: the angular resolution, which is the minimum angle between incident edges, and the crossing resolution, which is the minimum angle between crossing edges. We consider the total angular resolution of a graph, which is the maximum total angular resolution of a straight-line drawing of this graph. We prove tight bounds for the number of edges for graphs for some values of the total angular resolution up to a finite number of well specified exceptions of constant size. In addition, we show that deciding whether a graph has total angular resolution at least 60∘ is NP-hard. Further we present some special graphs and their total angular resolution.

We consider the problem of reforming an envy-free matching when each agent is assigned a single item. Given an envy-free matching, we consider an operation to exchange the item of an agent with an unassigned item preferred by the agent that results in another envy-free matching. We repeat this operation as long as we can. We prove that the resulting envy-free matching is uniquely determined up to the choice of an initial envy-free matching, and can be found in polynomial time. We call the resulting matching a reformist envy-free matching, and then we study a shortest sequence to obtain the reformist envy-free matching from an initial envy-free matching. We prove that a shortest sequence is computationally hard to obtain even when each agent accepts at most four items and each item is accepted by at most three agents. On the other hand, we give polynomial-time algorithms when each agent accepts at most three items or each item is accepted by at most two agents. Inapproximability and fixed-parameter (in)tractability are also discussed.

We consider the unlabeled motion-planning problem of $m$ unit-disc robots moving in a simple polygonal workspace of $n$ edges. The goal is to find a motion plan that moves the robots to a given set of $m$ target positions. For the unlabeled variant, it does not matter which robot reaches which target position as long as all target positions are occupied in the end. If the workspace has narrow passages such that the robots cannot fit through them, then the free configuration space, representing all possible unobstructed positions of the robots, will consist of multiple connected components. Even if in each component of the free space the number of targets matches the number of start positions, the motion-planning problem does not always have a solution when the robots and their targets are positioned very densely. In this paper, we prove tight bounds on how much separation between start and target positions is necessary to always guarantee a solution. Moreover, we describe an algorithm that always finds a solution in time $O(n \log n + mn + m^2)$ if the separation bounds are met. Specifically, we prove that the following separation is sufficient: any two start positions are at least distance $4$ apart, any two target positions are at least distance $4$ apart, and any pair of a start and a target positions is at least distance $3$ apart. We further show that when the free space consists of a single connected component, the separation between start and target positions is not necessary.

We initiate the study of k-edge-connected orientations of undirected graphs through edge flips for k ≥ 2. We prove that in every orientation of an undirected 2k-edge-connected graph, there exists a sequence of edges such that flipping their directions one by one does not decrease the edge-connectivity, and the final orientation is k-edge-connected. This yields an “edge-flip based” new proof of Nash-Williams' theorem: an undirected graph G has a k-edge-connected orientation if and only if G is 2k-edge-connected. As another consequence of the theorem, we prove that the edge-flip graph of k-edge-connected orientations of an undirected graph G is connected if G is (2k + 2)-edge-connected. This has been known to be true only when k = 1.

Abstract A graph $$G = (V,E)$$ G = ( V , E ) is a double-threshold graph if there exist a vertex-weight function $$w :V \rightarrow \mathbb {R}$$ w : V → R and two real numbers $$\mathtt {lb}, \mathtt {ub}\in \mathbb {R}$$ lb , ub ∈ R such that $$uv \in E$$ u v ∈ E if and only if $$\mathtt {lb}\le \mathtt {w}(u) + \mathtt {w}(v) \le \mathtt {ub}$$ lb ≤ w ( u ) + w ( v ) ≤ ub . In the literature, those graphs are studied also as the pairwise compatibility graphs that have stars as their underlying trees. We give a new characterization of double-threshold graphs that relates them to bipartite permutation graphs. Using the new characterization, we present a linear-time algorithm for recognizing double-threshold graphs. Prior to our work, the fastest known algorithm by Xiao and Nagamochi [Algorithmica 2020] ran in $$O(n^{3} m)$$ O ( n 3 m ) time, where n and m are the numbers of vertices and edges, respectively.

Motivated by adjacency in perfect matching polytopes, we study the shortest reconfiguration problem of perfect matchings via alternating cycles. Namely, we want to find a shortest sequence of perfect matchings which transforms one given perfect matching to another given perfect matching such that the symmetric difference of each pair of consecutive perfect matchings is a single cycle. The problem is equivalent to the combinatorial shortest path problem in perfect matching polytopes. We prove that the problem is NP-hard even when a given graph is planar or bipartite, but it can be solved in polynomial time when the graph is outerplanar.

Abstract In geographic data analysis, one is often given point data of different categories (such as facilities of a university categorized by department). Drawing upon recent research on set visualization, we want to visualize category membership by connecting points of the same category with visual links. Existing approaches that follow this path usually insist on connecting all members of a category, which may lead to many crossings and visual clutter. We propose an approach that avoids crossings between connections of different categories completely. Instead of connecting all data points of the same category, we subdivide categories into smaller, local clusters where needed. We do a case study comparing the legibility of drawings produced by our approach and those by existing approaches. In our problem formulation, we are additionally given a graph G on the data points whose edges express some sort of proximity. Our aim is to find a subgraph G′ of G with the following properties: (i) edges connect only data points of the same category, (ii) no two edges cross, and (iii) the number of connected components (clusters) is minimized. We then visualize the clusters in G′. For arbitrary graphs, the resulting optimization problem, Cluster Minimization, is NP‐hard (even to approximate). Therefore, we introduce two heuristics. We do an extensive benchmark test on real‐world data. Comparisons with exact solutions indicate that our heuristics do astonishing well for certain relative‐neighborhood graphs.

We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of n vertices and h holes. We introduce a graph of oriented distances to encode the distance between pairs of points of the domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in O ( min ⁡ ( n ω , n 2 + n h log ⁡ h + χ 2 ) ) time, where ω < 2.373 denotes the matrix multiplication exponent and χ ∈ Ω ( n ) ∩ O ( n 2 ) is the number of edges of the graph of oriented distances. We also provide an alternative algorithm for computing the diameter that runs in O ( n 2 log ⁡ n ) time.

Motivated by adjacency in perfect matching polytopes, we study the shortest reconfiguration problem of perfect matchings via alternating cycles. Namely, we want to find a shortest sequence of perfect matchings which transforms one given perfect matching to another given perfect matching such that the symmetric difference of each pair of consecutive perfect matchings is a single cycle. The problem is equivalent to the combinatorial shortest path problem in perfect matching polytopes. We prove that the problem is NP-hard even when a given graph is planar or bipartite, but it can be solved in polynomial time when the graph is outerplanar.

By folding the free-space diagram for efficient preprocessing, we show that the Frechet distance between 1D curves can be computed in O(nk log n) time, assuming one curve has ply k.

We present a protocol compiler of rational secret-sharing that converts any rational secret-sharing protocol to a protocol with an expected constant-round reconstruction. Our compiler can be applied to protocols for synchronous channels, and preserves a strict Nash equilibrium of the original protocol. Combining with an existing protocol, we obtain the first expected constant-round protocol that achieves a strict Nash equilibrium with the optimal coalition resilience ⌈n2⌉−1⁠, where n is the number of players. Our compiler can be extended to one that preserves the immunity to unexpectedly behaving players. For any constant m≥1⁠, we obtain an expected constant-round protocol that achieves a Nash equilibrium with the optimal coalition resilience ⌈n2⌉−m−1 in the presence of m unexpectedly behaving players. The protocol also achieves a strict Nash equilibrium. As a negative result, we show that if an expected constant-round protocol has immunity m>0⁠, then it cannot achieve a strict Nash equilibrium with the coalition resilience 2. Thus, our protocol with immunity achieves the optimal coalition resilience with respect to both Nash and strict Nash equilibrium.

Given a graph G=(V,E) with V={1,...,n}, we place on every vertex a token T_1,...,T_n. A swap is an exchange of tokens on adjacent vertices. We consider the algorithmic question of finding a shortest sequence of swaps such that token T_i is on vertex i. We are able to achieve essentially matching upper and lower bounds, for exact algorithms and approximation algorithms. For exact algorithms, we rule out any 2^{o(n)} algorithm under the ETH. This is matched with a simple 2^{O(n*log(n))} algorithm based on a breadth-first search in an auxiliary graph. We show one general 4-approximation and show APX-hardness. Thus, there is a small constant delta > 1 such that every polynomial time approximation algorithm has approximation factor at least delta. Our results also hold for a generalized version, where tokens and vertices are colored. In this generalized version each token must go to a vertex with the same color.

For a polygonal domain with h holes and a total of n vertices, we present algorithms that compute the L_1 geodesic diameter in O(n^2+h^4) time and the L_1 geodesic center in O((n^4+n^2 h^4)*alpha(n)) time, where alpha(.) denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in O(n^{7.73}) or O(n^7(h+log(n))) time, and compute the geodesic center in O(n^{12+epsilon}) time. Therefore, our algorithms are much faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on L_1 shortest paths in polygonal domains.

The field of exact exponential time algorithms for non-deterministic polynomial-time hard problems has thrived since the mid-2000s. While exhaustive search remains asymptotically the fastest known algorithm for some basic problems, non-trivial exponential time algorithms have been found for a myriad of problems, including G raph C oloring , H amiltonian P ath , D ominating S et , and 3-CNF-S at . In some instances, improving these algorithms further seems to be out of reach. The CNF-S at problem is the canonical example of a problem for which the trivial exhaustive search algorithm runs in time O (2 n ), where n is the number of variables in the input formula. While there exist non-trivial algorithms for CNF-S at that run in time o (2 n ), no algorithm was able to improve the growth rate 2 to a smaller constant, and hence it is natural to conjecture that 2 is the optimal growth rate. The strong exponential time hypothesis (SETH) by Impagliazzo and Paturi [JCSS 2001] goes a little bit further and asserts that, for every ϵ < 1, there is a (large) integer k such that k -CNF-S at cannot be computed in time 2 ϵ n . In this article, we show that, for every ϵ < 1, the problems H itting S et , S et S plitting , and NAE-S at cannot be computed in time O (2 ϵ n ) unless SETH fails. Here n is the number of elements or variables in the input. For these problems, we actually get an equivalence to SETH in a certain sense. We conjecture that SETH implies a similar statement for S et C over and prove that, under this assumption, the fastest known algorithms for S teiner T ree , C onnected V ertex C over , S et P artitioning , and the pseudo-polynomial time algorithm for S ubset S um cannot be significantly improved. Finally, we justify our assumption about the hardness of S et C over by showing that the parity of the number of solutions to S et C over cannot be computed in time O (2 ϵ n ) for any ϵ < 1 unless SETH fails.

We study the impact of metric constraints on the realizability of planar graphs. Let G be a subgraph of a planar graph H (where H is the "host" of G). The graph G is free in H if for every choice of positive lengths for the edges of G, the host H has a planar straight-line embedding that realizes these lengths; and G is extrinsically free in H if all constraints on the edge lengths of G depend on G only, irrespective of additional edges of the host H.

Given a polygonal region containing a target point (which we assume is the origin), it is not hard to see that there are two points on the perimeter that are antipodal, i.e., whose midpoint is the origin. We prove three generalizations of this fact. (1) For any polygon (or any bounded closed region with connected boundary) containing the origin, it is possible to place a given set of weights on the boundary so that their barycenter (center of mass) coincides with the origin, provided that the largest weight does not exceed the sum of the other weights. (2) On the boundary of any 3-dimensional bounded polyhedron containing the origin, there exist three points that form an equilateral triangle centered at the origin. (3) On the 1-skeleton of any 3-dimensional bounded convex polyhedron containing the origin, there exist three points whose center of mass coincides with the origin.

We give a necessary condition and a sufficient condition for a minimum-cost spanning tree game introduced by Bird to be submodular (or convex). When the cost is restricted to two values, we give a characterization of submodular minimum-cost spanning tree games. We also discuss algorithmic issues.Copyright © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(3), 231–238 2014

The field of exact exponential time algorithms for NP-hard problems has thrived over the last decade. While exhaustive search remains asymptotically the fastest known algorithm for some basic problems, difficult and non-trivial exponential time algorithms have been found for a myriad of problems, including GRAPH COLORING, HAMILTONIAN PATH, DOMINATING SET and 3-CNF-SAT. In some instances, improving these algorithms further seems to be out of reach. The CNF-SAT problem is the canonical example of a problem for which the trivial exhaustive search algorithm runs in time O(2n), where n is the number of variables in the input formula. While there exist non-trivial algorithms for CNF-SAT that run in time o(2n), no algorithm was able to improve the growth rate 2 to a smaller constant, and hence it is natural to conjecture that 2 is the optimal growth rate. The strong exponential time hypothesis (SETH) by Impagliazzo and Paturi [JCSS 2001] goes a little bit further and asserts that, for every ϵϵn. In this paper, we show that, for every ϵϵn) unless SETH fails. Here n is the number of elements or variables in the input. For these problems, we actually get an equivalence to SETH in a certain sense. We conjecture that SETH implies a similar statement for SET COVER, and prove that, under this assumption, the fastest known algorithms for STEINTER TREE, CONNECTED VERTEX COVER, SET PARTITIONING, and the pseudo-polynomial time algorithm for SUBSET SUM cannot be significantly improved. Finally, we justify our assumption about the hardness of SET COVER by showing that the parity of the number of set covers.

A binary tanglegram is a drawing of a pair of rooted binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example, in phylogenetics, it is essential that both trees are drawn without edge crossings and that the inter-tree edges have as few crossings as possible. It is known that finding a tanglegram with the minimum number of crossings is NP-hard and that the problem is fixed-parameter tractable with respect to that number. We prove that under the Unique Games Conjecture there is no constant-factor approximation for binary trees. We show that the problem is NP-hard even if both trees are complete binary trees. For this case we give an O(n 3)-time 2-approximation and a new, simple fixed-parameter algorithm. We show that the maximization version of the dual problem for binary trees can be reduced to a version of MaxCut for which the algorithm of Goemans and Williamson yields a 0.878-approximation.

A straight-line drawing δ of a planar graph G need not be plane but can be made so by untangling it, that is, by moving some of the vertices of G. Let shift(G,δ) denote the minimum number of vertices that need to be moved to untangle δ. We show that shift(G,δ) is NP-hard to compute and to approximate. Our hardness results extend to a version of 1BendPointSetEmbeddability, a well-known graph-drawing problem. Further we define fix(G,δ)=n−shift(G,δ) to be the maximum number of vertices of a planar n-vertex graph G that can be fixed when untangling δ. We give an algorithm that fixes at least $\sqrt{((\log n)-1)/\log\log n}$ vertices when untangling a drawing of an n-vertex graph G. If G is outerplanar, the same algorithm fixes at least $\sqrt{n/2}$ vertices. On the other hand, we construct, for arbitrarily large n, an n-vertex planar graph G and a drawing δ G of G with $\ensuremath {\mathrm {fix}}(G,\delta_{G})\leq \sqrt{n-2}+1$ and an n-vertex outerplanar graph H and a drawing δ H of H with $\ensuremath {\mathrm {fix}}(H,\delta_{H})\leq2\sqrt{n-1}+1$ . Thus our algorithm is asymptotically worst-case optimal for outerplanar graphs.