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 @math vertices when untangling a drawing of an n-vertex graph G. If G is outerplanar, the same algorithm fixes at least @math vertices. On the other hand, we construct, for arbitrarily large n, an n-vertex planar graph G and a drawing δ G of G with @math and an n-vertex outerplanar graph H and a drawing δ H of H with @math . Thus our algorithm is asymptotically worst-case optimal for outerplanar graphs.
Verbitsky @cite_22 investigated planar graphs of higher connectivity. He proved linear upper bounds on @math for three- and four-connected planar graphs. Cibulka @cite_3 gave, for any planar graph @math , an upper bound on @math that is a function of the number of vertices, the maximum degree, and the diameter of @math . This latter bound implies, in particular, that @math for any three-connected planar graph @math and that any graph @math such that @math for some @math must have a vertex of degree @math .
@cite_22 @cite_3
2161190897 2034501275 2399682168 1968429800
We present algorithmic and hardness results for network design problems with degree or order constraints. The first problem we consider is the Survivable Network Design problem with degree constraints on vertices. The objective is to find a minimum cost subgraph which satisfies connectivity requirements between vertices and also degree upper bounds @math on the vertices. This includes the well-studied Minimum Bounded Degree Spanning Tree problem as a special case. Our main result is a @math -approximation algorithm for the edge-connectivity Survivable Network Design problem with degree constraints, where the cost of the returned solution is at most twice the cost of an optimum solution (satisfying the degree bounds) and the degree of each vertex @math is at most @math . This implies the first constant factor (bicriteria) approximation algorithms for many degree constrained network design problems, including the Minimum Bounded Degree Steiner Forest problem. Our results also extend to directed graphs and provide the first constant factor (bicriteria) approximation algorithms for the Minimum Bounded Degree Arborescence problem and the Minimum Bounded Degree Strongly @math -Edge-Connected Subgraph problem. In contrast, we show that the vertex-connectivity Survivable Network Design problem with degree constraints is hard to approximate, even when the cost of every edge is zero. A striking aspect of our algorithmic result is its simplicity. It is based on the iterative relaxation method, which is an extension of Jain's iterative rounding method. This provides an elegant and unifying algorithmic framework for a broad range of network design problems. We also study the problem of finding a minimum cost @math -edge-connected subgraph with at least @math vertices, which we call the @math -subgraph problem. This generalizes some well-studied classical problems such as the @math -MST and the minimum cost @math -edge-connected subgraph problems. We give a polylogarithmic approximation for the @math -subgraph problem. However, by relating it to the Densest @math -Subgraph problem, we provide evidence that the @math -subgraph problem might be hard to approximate for arbitrary @math . We consider the problem of labeling the nodes of a graph in a way that will allow one to compute the distance between any two nodes directly from their labels (without using any additional information). Our main interest is in the minimal length of labels needed in different cases. We obtain upper and lower bounds for several interesting families of graphs. In particular, our main results are the following. For general graphs, we show that the length needed is Θ(n). For trees, we show that the length needed is Θ(log2 n). For planar graphs, we show an upper bound of O(√nlogn) and a lower bound of Ω(n1 3). For bounded degree graphs, we show a lower bound of Ω(√n). The upper bounds for planar graphs and for trees follow by a more general upper bound for graphs with a r(n)-separator. The two lower bounds, however, are obtained by two different arguments that may be interesting in their own right. We also show some lower bounds on the length of the labels, even if it is only required that distances be approximated to a multiplicative factor s. For example, we show that for general graphs the required length is Ω(n) for every s < 3. We also consider the problem of the time complexity of the distance function once the labels are computed. We show that there are graphs with optimal labels of length 3 log n, such that if we use any labels with fewer than n bits per label, computing the distance function requires exponential time. A similar result is obtained for planar and bounded degree graphs. We develop a new technique for constructing sparse graphs that allow us to prove near-linear lower bounds on the round complexity of computing distances in the CONGEST model. Specifically, we show an @math lower bound for computing the diameter in sparse networks, which was previously known only for dense networks [, SODA 2012]. In fact, we can even modify our construction to obtain graphs with constant degree, using a simple but powerful degree-reduction technique which we define. Moreover, our technique allows us to show @math lower bounds for computing @math -approximations of the diameter or the radius, and for computing a @math -approximation of all eccentricities. For radius, we are unaware of any previous lower bounds. For diameter, these greatly improve upon previous lower bounds and are tight up to polylogarithmic factors [, SODA 2012], and for eccentricities the improvement is both in the lower bound and in the approximation factor [Holzer and Wattenhofer, PODC 2012]. Interestingly, our technique also allows showing an almost-linear lower bound for the verification of @math -spanners, for @math . We study the quantitative geometry of graphs in terms of their genus, using the structure of certain "cut graphs," i.e. subgraphs whose removal leaves a planar graph. In particular, we give optimal bounds for random partitioning schemes, as well as various types of embeddings. Using these geometric primitives, we present exponentially improved dependence on genus for a number of problems like approximate max-flow min-cut theorems, approximations for uniform and nonuniform Sparsest Cut, treewidth approximation, Laplacian eigenvalue bounds, and Lipschitz extension theorems and related metric labeling problems. We list here a sample of these improvements. All the following statements refer to graphs of genus g, unless otherwise noted. • We show that such graphs admit an O(log g)-approximate multi-commodity max-flow min-cut theorem for the case of uniform demands. This bound is optimal, and improves over the previous bound of O(g) [KPR93, FT03]. For general demands, we show that the worst possible gap is O(log g + CP), where CP is the gap for planar graphs. This dependence is optimal, and already yields a bound of O(log g + √log n), improving over the previous bound of O(√g log n) [KLMN04]. • We give an O(√log g)-approximation for the uniform Sparsest Cut, balanced vertex separator, and treewidth problems, improving over the previous bound of O(g) [FHL05]. • If a graph G has genus g and maximum degree D, we show that the kth Laplacian eigenvalue of G is (log g)2 · O(kgD n), improving over the previous bound of g2·O(kgD n) [KLPT09]. There is a lower bound of Ω(kgD n), making this result almost tight. • We show that if (X, d) is the shortest-path metric on a graph of genus g and S ⊆ X, then every L-Lipschitz map f: S → Z into a Banach space Z admits an O(L log g)-Lipschitz extension f: X → Z. This improves over the previous bound of O(Lg) [LN05], and compares to a lower bound of Ω(L√log g). In a related way, we show that there is an O(log g)-approximation for the 0-extension problem on such graphs, improving over the previous O(g) bound. • We show that every n-vertex shortest-path metric on a graph of genus g embeds into L2 with distortion O(log g + √log n), improving over the previous bound of O(√g log n). Our result is asymptotically optimal for every dependence g = g(n).