The thickness of a graph @math with @math vertices is the minimum number of planar subgraphs of @math whose union is @math . A polyline drawing of @math in @math is a drawing @math of @math , where each vertex is mapped to a point and each edge is mapped to a polygonal chain. Bend and layer complexities are two important aesthetics of such a drawing. The bend complexity of @math is the maximum number of bends per edge in @math , and the layer complexity of @math is the minimum integer @math such that the set of polygonal chains in @math can be partitioned into @math disjoint sets, where each set corresponds to a planar polyline drawing. Let @math be a graph of thickness @math . By F ' a ry's theorem, if @math , then @math can be drawn on a single layer with bend complexity @math . A few extensions to higher thickness are known, e.g., if @math (resp., @math ), then @math can be drawn on @math layers with bend complexity 2 (resp., @math ). However, allowing a higher number of layers may reduce the bend complexity, e.g., complete graphs require @math layers to be drawn using 0 bends per edge. In this paper we present an elegant extension of F ' a ry's theorem to draw graphs of thickness @math . We first prove that thickness- @math graphs can be drawn on @math layers with @math bends per edge. We then develop another technique to draw thickness- @math graphs on @math layers with bend complexity, i.e., @math , where @math . Previously, the bend complexity was not known to be sublinear for @math . Finally, we show that graphs with linear arboricity @math can be drawn on @math layers with bend complexity @math .
Given an @math -vertex planar graph @math and a point location for each vertex in @math , Pach and Wenger @cite_11 showed that @math admits a planar polyline drawing with the given vertex locations, where each edge has at most @math bends. They also showed that @math bends are sometimes necessary. @cite_3 and Gordon @cite_4 independently improved the bend complexity to @math . Consequently, for @math , these constructions can be used to draw @math on @math layers with at most @math bends per edge.
@cite_4 @cite_3 @cite_11
2063120809 1483246560
We consider graphs that admit polyline drawings where all crossings occur at the same angle @math . We prove that every graph on @math vertices that admits such a polyline drawing with at most two bends per edge has @math edges. This result remains true when each crossing occurs at an angle from a small set of angles. We also provide several extensions that might be of independent interest. Let G be a planar graph with n vertices and with a partition of the vertex set into subsets V"0,...,V"k"-"1 for some positive integer [email protected][email protected]?n. Let S be a set of n distinct points in the plane with a partition into subsets S"0,...,S"k"-"1 with |V"i|=|S"i| ([email protected][email protected]?k-1). This paper studies the problem of computing a planar polyline drawing of G, such that each vertex of V"i is mapped to a distinct point of S"i. Lower and upper bounds on the number of bends per edge are proved for any [email protected][email protected]?n. In the special case k=n, we improve the upper and lower bounds presented in a paper by Pach and Wenger [J. Pach, R. Wenger, Embedding planar graphs at fixed vertex locations, Graphs and Combinatorics 17 (2001) 717-728]. The upper bound is based on an algorithm for computing a topological book embedding of a planar graph, such that the vertices follow a given left-to-right order and the number of crossings between every edge and the spine is asymptotically optimal, which can be regarded as a result of independent interest. A directed graph is upward planar if it can be drawn in the plane such that every edge is a monotonically increasing curve in the vertical direction and no two edges cross. An undirected graph is rectilinear planar if it can be drawn in the plane such that every edge is a horizontal or vertical segment and no two edges cross. Testing upward planarity and rectilinear planarity are fundamental problems in the effective visualization of various graph and network structures. For example, upward planarity is useful for the display of order diagrams and subroutine-call graphs, while rectilinear planarity is useful for the display of circuit schematics and entity-relationship diagrams. We show that upward planarity testing and rectilinear planarity testing are NP-complete problems. We also show that it is NP-hard to approximate the minimum number of bends in a planar orthogonal drawing of an n-vertex graph with an @math error for any @math . A straight-line grid embedding of a planar graph is a drawing of the graph on a plane where the vertices are located at grid points and the edges are represented by nonintersecting segments of straight, lines joining their incident vertices. Given an n-vertex embedded planar graph with @math , a straight-line embedding on a grid of size @math can be computed deterministically in @math time with @math processors. If randomization is used, the complexity is improved to @math expected time with the same optimal linear work. These algorithms run on a parallel random access machine that allows concurrent reads and concurrent writes of the shared memory and permits an arbitrary processor to succeed in case of a write conflict. We consider distance queries in vertex-labeled planar graphs. For any fixed @math we show how to preprocess a directed planar graph with vertex labels and arc lengths into a data structure that answers queries of the following form. Given a vertex @math and a label @math return a @math -approximation of the distance from @math to its closest vertex with label @math . For a directed planar graph with @math vertices, such that the ratio of the largest to smallest arc length is bounded by @math , the preprocessing time is @math , the data structure size is @math , and the query time is @math . We also point out that a vertex label distance oracle for undirected planar graphs suggested in an earlier version of this paper is incorrect. A problem arising in the design of vacuum systems and having applications to some natural problems of interconnection design is described as follows. (1) Given a set X and subsets @math of @math , satisfying @math , find a graph G with vertex set X and the minimum number of edges such that for any i, the subgraph induced by @math has a connected component containing @math .Two other problems related to this one are the following ones. (2) Given a set X and subsets @math such that @math , find a graph G with vertex set X and the minimum number of edges such that for any i the subgraph @math induced by @math in G is connected. (3) Given a set X and subsets @math such that @math , find a graph G with vertex set X, find a graph G with vertex set X and the minimum number of edges such that for any subset I of @math , the subgraph induced by @math is co... Given a graph G with n vertices and a set S of n points in the plane, a point-set embedding of G on S is a planar drawing such that each vertex of G is mapped to a distinct point of S. A geometric point-set embedding is a point-set embedding with no edge bends. This paper studies the following problem: The input is a set S of n points, a planar graph G with n vertices, and a geometric point-set embedding of a subgraph G^'@?G on a subset of S. The desired output is a point-set embedding of G on S that includes the given partial drawing of G^'. We concentrate on trees and show how to compute the output in O(n^2logn) time in a real-RAM model and with at most n-k edges with at most [email protected]?k [email protected]? bends, where k is the number of vertices of the given subdrawing. We also prove that there are instances of the problem which require at least k-3 bends on n-k edges. Given a planar graph G together with a planar representation P, a region preserving grid embedding of G is a planar embedding of G in the rectilinear grid that has planar representation isomorphic to P. In this paper, an algorithm is presented that computes a region preserving grid embedding with the minimum number of bends in edges. This algorithm makes use of network flow techniques, and runs in time @math , where n is the number of vertices of the graph. Constrained versions of the problem are also considered, and most results are extended to k-gonal graphs, i.e., graphs whose edges are sequences of segments with slope multiple of @math degrees. Applications of the above results can be found in several areas: VLSI circuit layout, architectural design, communication by light or microwave, transportation problems, and automatic layout of graphlike diagrams. Problems of finding p-centers and dominating sets of radius r in networks are discussed in this paper. Let n be the number of vertices and @math be the number of edges of a network. With the assumption that the distance-matrix of the network is available, we design an @math algorithm for finding an absolute 1-center of a vertex-weighted network and an @math algorithm for finding an absolute 1-center of a vertex-unweighted network (the problem of finding a vertex 1-center of a network is trivial). We show that the problem of finding a (vertex or absolute) p-center (for @math ) of a (vertex-weighted or vertex-unweighted) network, and the problem of finding a dominating set of radius r are @math -hard even in the case where the network has a simple structure (e.g., a planar graph of maximum vertex degree 3). However, we describe an algorithm of complexity @math (respectively, $ O[| E |^p n^ 2p - 1... In a coalescing random walk, a set of particles make independent discrete-time random walks on a graph. Whenever one or more particles meet at a vertex, they unite to form a single particle, which then continues a random walk through the graph. Let @math be an undirected and connected graph with @math vertices and @math edges. The coalescence time, @math , is the expected time for all particles to coalesce, when initially one particle is located at each vertex. We study the problem of bounding the coalescence time for general connected graphs and prove that @math . Here @math is the second eigenvalue of the transition matrix of the random walk. To avoid problems arising from, e.g., lack of coalescence on bipartite graphs, we assume the random walk can be made lazy if required. The value of @math is given by @math , where @math is the degree of vertex @math , and @math is the average degree. The parame... We address the following problem: Given a complete @math -partite geometric graph @math whose vertex set is a set of @math points in @math , compute a spanner of @math that has a “small” stretch factor and “few” edges. We present two algorithms for this problem. The first algorithm computes a @math -spanner of @math with @math edges in @math time. The second algorithm computes a @math -spanner of @math with @math edges in @math time. The latter result is optimal: We show that for any @math , spanners with @math edges and stretch factor less than 3 do not exist for all complete @math -partite geometric graphs. Abstract A drawing of a graph is 1-planar if each edge is crossed at most once. A graph is 1-planar if it has a 1-planar drawing. A k-bend RAC (Right Angle Crossing) drawing of a graph is a polyline drawing where each edge has at most k bends and edges cross only at right angles. A graph is k-bend RAC if it has a k -bend RAC drawing. A 0-bend RAC graph (drawing) is also called a straight-line RAC graph (drawing) . The relationships between 1-planar and k -bend RAC graphs have been partially studied in the literature. It is known that there are both 1-planar graphs that are not straight-line RAC and straight-line RAC graphs that are not 1-planar. The existence of 1-planar straight-line RAC drawings has been proven only for restricted families of 1-planar graphs. Two of the main questions still open are: ( i ) What is the complexity of deciding whether a graph has a drawing that is both 1-planar and straight-line RAC? ( i i ) Does every 1-planar graph have a drawing that is both 1-planar and 1-bend RAC? In this paper we answer these two questions. Namely, we prove an NP-hardness result for the first question, and we positively answer the second question by describing a drawing algorithm for 1-planar graphs. In this paper we study the Steiner tree problem over a dynamic set of terminals. We consider the model where we are given an @math -vertex graph @math with positive real edge weights, and our goal is to maintain a tree which is a good approximation of the minimum Steiner tree spanning a terminal set @math , which changes over time. The changes applied to the terminal set are either terminal additions (incremental scenario), terminal removals (decremental scenario), or both (fully dynamic scenario). Our task here is twofold. We want to support updates in sublinear @math time, and keep the approximation factor of the algorithm as small as possible. We show that we can maintain a @math -approximate Steiner tree of a general graph in @math time per terminal addition or removal. Here, @math denotes the stretch of the metric induced by @math . For planar graphs we achieve the same running time and the approximation ratio of @math . Moreover, we show faster algorithms for incremental and decremental scenarios. Finally, we show that if we allow higher approximation ratio, even more efficient algorithms are possible. In particular we show a polylogarithmic time @math -approximate algorithm for planar graphs. One of the main building blocks of our algorithms are dynamic distance oracles for vertex-labeled graphs, which are of independent interest. We also improve and use the online algorithms for the Steiner tree problem. In this paper, we study the problem of drawing a given planar graph such that vertices are at pre-specified points and the entire drawing is inside a given polygon. We give a method that shows that for an n-vertex graph and a k-sided polygon, Θ(kn2) bends are always sufficient. We also give an example of a graph where Θ(kn2) bends are necessary for such a drawing. The simultaneous embedding problem is, given two planar graphs G1=(V,E1) and G2=(V,E2), to find planar embeddings ϕ(G1) and ϕ(G2) such that each vertex v∈V is mapped to the same point in ϕ(G1) and in ϕ(G2). This article presents a linear-time algorithm for the simultaneous embedding problem such that edges are drawn as polygonal chains with at most two bends and all vertices and all bends of the edges are placed on a grid of polynomial size. An extension of this problem with so-called fixed edges is also considered A further linear-time algorithm of this article solves the following problem: Given a planar graph G and a set of distinct points, find a planar embedding for G that maps each vertex to one of the given points. The solution presented also uses at most two bends per edge and a grid whose size is polynomial in the size of the grid that includes all given points. An example shows two bends per edge to be optimal The Euclidean @math -means problem is a classical problem that has been extensively studied in the theoretical computer science, machine learning and the computational geometry communities. In this problem, we are given a set of @math points in Euclidean space @math , and the goal is to choose @math centers in @math so that the sum of squared distances of each point to its nearest center is minimized. The best approximation algorithms for this problem include a polynomial time constant factor approximation for general @math and a @math -approximation which runs in time @math . At the other extreme, the only known computational complexity result for this problem is NP-hardness [ADHP'09]. The main difficulty in obtaining hardness results stems from the Euclidean nature of the problem, and the fact that any point in @math can be a potential center. This gap in understanding left open the intriguing possibility that the problem might admit a PTAS for all @math . In this paper we provide the first hardness of approximation for the Euclidean @math -means problem. Concretely, we show that there exists a constant @math such that it is NP-hard to approximate the @math -means objective to within a factor of @math . We show this via an efficient reduction from the vertex cover problem on triangle-free graphs: given a triangle-free graph, the goal is to choose the fewest number of vertices which are incident on all the edges. Additionally, we give a proof that the current best hardness results for vertex cover can be carried over to triangle-free graphs. To show this we transform @math , a known hard vertex cover instance, by taking a graph product with a suitably chosen graph @math , and showing that the size of the (normalized) maximum independent set is almost exactly preserved in the product graph using a spectral analysis, which might be of independent interest. We present an algorithm for testing the k-vertex-connectivity of graphs with the given maximum degree. The time complexity of the algorithm is independent of the number of vertices and edges of graphs. Fixed degree bound d, a graph G with n vertices and a maximum degree at most d is called e-far from k-vertex-connectivity when at least @math edges must be added to or removed from G to obtain a k-vertex-connected graph with a maximum degree at most d. The algorithm always accepts every graph that is k-vertex-connected and rejects every graph that is e-far from k-vertex-connectivity with a probability of at least 2 3. The algorithm runs in @math time (c>1 is a constant) for (k−1)-vertex-connected graphs, and in @math time (c>1 is a constant) for general graphs. It is the first constant-time k-vertex-connectivity testing algorithm for general k≥4. This paper investigates a zero-sum game played on a weighted connected graph @math between two players, the tree player and the edge player. At each play, the tree player chooses a spanning tree @math and the edge player chooses an edge @math . The payoff to the edge player is @math , defined as follows: If @math lies in the tree @math then @math ; if @math does not lie in the tree then @math , where @math is the weight of edge @math and @math is the weight of the unique cycle formed when edge @math is added to the tree @math . The main result is that the value of the game on any @math -vertex graph is bounded above by @math . It is conjectured that the value of the game is @math . The game arises in connection with the @math -server problem on a road network; i.e., a metric space that can be represented as a multigraph @math in which each edge @math represents a road of length @math . It is shown that, if the value of the game on @math is @math , then there is a randomized strategy that achieves a competitive ratio of @math against any oblivious adversary. Thus, on any @math -vertex road network, there is a randomized algorithm for the @math -server problem that is @math competitive against oblivious adversaries. At the heart of the analysis of the game is an algorithm that provides an approximate solution for the simple network design problem. Specifically, for any @math -vertex weighted, connected multigraph, the algorithm constructs a spanning tree @math such that the average, over all edges @math , of @math is less than or equal to @math . This result has potential application to the design of communication networks. It also improves substantially known estimates concerning the existence of a sparse basis for the cycle space of a graph. This paper studies labeling schemes for flow and connectivity functions. A flow labeling scheme using @math -bit labels is presented for general n-vertex graphs with maximum (integral) capacity @math . This is shown to be asymptotically optimal. For edge-connectivity, this yields a tight bound of @math bits. A k-vertex connectivity labeling scheme is then given for general n-vertex graphs using at most 3 log n bits for k = 2, 5 log n bits for k = 3, and 2k log n bits for k > 3. Finally, a lower bound of @math is established for k -vertex connectivity on n-vertex graphs, where k is polylogarithmic in n. Given a large edge-weighted network @math with @math terminal vertices, we wish to compress it and store, using little memory, the value of the minimum cut (or equivalently, maximum flow) between every bipartition of terminals. One appealing methodology to implement a compression of @math is to construct a : a small network @math with the same @math terminals, in which the minimum cut value between every bipartition of terminals is the same as in @math . This notion was introduced by Hagerup, Katajainen, Nishimura, and Ragde [JCSS '98], who proved that such @math of size at most @math always exists. Obviously, by having access to the smaller network @math , certain computations involving cuts can be carried out much more efficiently. We provide several new bounds, which together narrow the previously known gap from doubly-exponential to only singly-exponential, both for planar and for general graphs. Our first and main result is that every @math -terminal planar network admits a mimicking network @math of size @math , which is moreover a minor of @math . On the other hand, some planar networks @math require @math . For general networks, we show that certain bipartite graphs only admit mimicking networks of size @math , and moreover, every data structure that stores the minimum cut value between all bipartitions of the terminals must use @math machine words.