共查询到20条相似文献,搜索用时 62 毫秒
1.
Let G be a planar graph of n vertices, v
1,…,v
n
, and let {p
1,…,p
n
} be a set of n points in the plane. We present an algorithm for constructing in O(n
2) time a planar embedding of G, where vertex v
i
is represented by point p
i
and each edge is represented by a polygonal curve with O(n) bends (internal vertices). This bound is asymptotically optimal in the worst case. In fact, if G is a planar graph containing at least m pairwise independent edges and the vertices of G are randomly assigned to points in convex position, then, almost surely, every planar embedding of G mapping vertices to their assigned points and edges to polygonal curves has at least m/20 edges represented by curves with at least m/403 bends.
Received: May 24, 1999 Final version received: April 10, 2000 相似文献
2.
John R Gilbert Joan P Hutchinson Robert Endre Tarjan 《Journal of Algorithms in Cognition, Informatics and Logic》1984,5(3):391-407
Many divide-and-conquer algorithms on graphs are based on finding a small set of vertices or edges whose removal divides the graph roughly in half. Most graphs do not have the necessary small separators, but some useful classes do. One such class is planar graphs: If an n-vertex graph can be drawn on the plane, then it can be bisected by removal of O(sqrt(n)) vertices (R. J. Lipton and R. E. Tarjan, SIAM J. Appl. Math.36 (1979), 177–189). The main result of the paper is that if a graph can be drawn on a surface of genus g, then it can be bisected by removal of O(sqrt(gn)) vertices. This bound is best possible to within a constant factor. An algorithm is given for finding the separator that takes time linear in the number of edges in the graph, given an embedding of the graph in its genus surface. Some extensions and applications of these results are discussed. 相似文献
3.
Jan Kyn?l 《Discrete Mathematics》2009,309(7):1917-1923
We study the existence of edges having few crossings with the other edges in drawings of the complete graph (more precisely, in simple topological complete graphs). A topological graphT=(V,E) is a graph drawn in the plane with vertices represented by distinct points and edges represented by Jordan curves connecting the corresponding pairs of points (vertices), passing through no other vertices, and having the property that any intersection point of two edges is either a common end-point or a point where the two edges properly cross. A topological graph is simple if any two edges meet in at most one common point.Let h=h(n) be the smallest integer such that every simple topological complete graph on n vertices contains an edge crossing at most h other edges. We show that Ω(n3/2)≤h(n)≤O(n2/log1/4n). We also show that the analogous function on other surfaces (torus, Klein bottle) grows as cn2. 相似文献
4.
Computing Vertex Connectivity: New Bounds from Old Techniques 总被引:1,自引:0,他引:1
Monika R. Henzinger Satish Rao Harold N. Gabow 《Journal of Algorithms in Cognition, Informatics and Logic》2000,34(2):222
The vertex connectivity κ of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the vertex connectivity and a corresponding separator. The time for a digraph having n vertices and m edges is O(min{κ3 + n, κn}m); for an undirected graph the term m can be replaced by κn. A randomized algorithm finds κ with error probability 1/2 in time O(nm). If the vertices have nonnegative weights the weighted vertex connectivity is found in time O(κ1nmlog(n2/m)) where κ1 ≤ m/n is the unweighted vertex connectivity or in expected time O(nmlog(n2/m)) with error probability 1/2. The main algorithm combines two previous vertex connectivity algorithms and a generalization of the preflow-push algorithm of Hao and Orlin (1994, J. Algorithms17, 424–446) that computes edge connectivity. 相似文献
5.
We consider the problem of finding a sparse set of edges containing the minimum spanning tree (MST) of a random subgraph of G with high probability. The two random models that we consider are subgraphs induced by a random subset of vertices, each vertex included independently with probability p, and subgraphs generated as a random subset of edges, each edge with probability p. Let n denote the number of vertices, choose p ∈ (0, 1) possibly depending on n, and let b = 1/(1 ? p). We show that in both random models, for any weighted graph G, there is a set of edges Q of cardinality O(n logbn) that contains the minimum spanning tree of a random subgraph of G with high probability. This result is asymptotically optimal. As a consequence, we also give a bound of O(kn) on the size of the union of all minimum spanning trees of G with some k vertices (or edges) removed. More generally, we show a bound of O(n logbn) on the size of a covering set in a matroid of rank n, which contains the minimum‐weight basis of a random subset with high probability. Also, we give a randomized algorithm that calls an MST subroutine only a polylogarithmic number of times and finds the covering set with high probability. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006 相似文献
6.
Farhad Shahrokhi Lszl A. Szkely Ondrej Sýkora Imrich Vrt'o 《Journal of Graph Theory》1996,21(4):413-424
Let G be a graph on n vertices and m edges. The book crossing number of G is defined as the minimum number of edge crossings when the vertices of G are placed on the spine of a k-page book and edges are drawn on pages, such that each edge is contained by one page. Our main results are two polynomial time algorithms to generate near optimal drawing of G on books. The first algorithm give an O(log2 n) times optimal solution, on small number of pages, under some restrictions. This algorithm also gives rise to the first polynomial time algorithm for approximating the rectilinear crossing number so that the coordinates of vertices in the plane are small integers, thus resolving a recent open question concerning the rectilinear crossing number. Moreover, using this algorithm we improve the best known upper bounds on the rectilinear crossing number. The second algorithm generates a drawing of G with O(m2/k2) crossings on k pages. This is within a constant multiplicative factor from our general lower bound of Ω(m3/n2k2), provided that m = Ψ(n2). © 1996 John Wiley & Sons, Inc. 相似文献
7.
Giorgio Ausiello Giuseppe F. Italiano Alberto Marchetti Spaccamela Umberto Nanni 《Journal of Algorithms in Cognition, Informatics and Logic》1991,12(4)
We consider the problem of maintaining on-line a solution to the All Pairs Shortest Paths Problem in a directed graph G = (V,E) where edges may be dynamically inserted or have their cost decreased. For the case of integer edge costs in a given range [1…C], we introduce a new data structure which is able to answer queries concerning the length of the shortest path between any two vertices in constant time and to trace out the shortest path between any two vertices in time linear in the number of edges reported. The total time required to maintain the data structure under a sequence of at most O(n2) edge insertions and at most O(Cn2) edge cost decreases is O(Cn3 log(nC)) in the worst case, where n is the total number of vertices in G. For the case of unit edge costs, the total time required to maintain the data structure under a sequence of at most O(n2) insertions of edges becomes O(n3 logn) in the worst case. The same bounds can be achieved for the problem of maintaining on-line longest paths in directed acyclic graphs. All our algorithms improve previously known algorithms and are only a logarithmic factor away from the best possible bounds. 相似文献
8.
The subgraph homeomorphism problem is to decide if there is an injective mapping of the vertices of a pattern graph into vertices of a host graph so that the edges of the pattern graph can be mapped into (internally) vertex-disjoint paths in the host graph. The restriction of subgraph homeomorphism where an injective mapping of the vertices of the pattern graph into vertices of the host graph is already given in the input instance is termed fixed-vertex subgraph homeomorphism.We show that fixed-vertex subgraph homeomorphism for a pattern graph on p vertices and a host graph on n vertices can be solved in time 2n−pnO(1) or in time 3n−pnO(1) and polynomial space. In effect, we obtain new non-trivial upper bounds on the time complexity of the problem of finding k vertex-disjoint paths and general subgraph homeomorphism. 相似文献
9.
Josef Cibulka 《Discrete and Computational Geometry》2010,43(2):402-411
Untangling is a process in which some vertices in a drawing of a planar graph are moved to obtain a straight-line plane drawing.
The aim is to move as few vertices as possible. We present an algorithm that untangles the cycle graph C
n
while keeping Ω(n
2/3) vertices fixed.
For any connected graph G, we also present an upper bound on the number of fixed vertices in the worst case. The bound is a function of the number
of vertices, maximum degree, and diameter of G. One consequence is that every 3-connected planar graph has a drawing δ such that at most O((nlog n)2/3) vertices are fixed in every untangling of δ. 相似文献
10.
We study empty pseudo-triangles in a set P of n points in the plane, where an empty pseudo-triangle has its vertices at the points of P, and no points of P lie inside. We give bounds on the minimum and maximum number of empty pseudo-triangles. If P lies inside a triangle whose corners must be the convex vertices of the pseudo-triangle, then there can be between Θ(n2) and Θ(n3) empty pseudo-triangles. If the convex vertices of the pseudo-triangle are also chosen from P, this number lies between Θ(n3) and Θ(n6). If we count only star-shaped pseudo-triangles, the bounds are Θ(n2) and Θ(n5). We also study optimization problems: minimizing or maximizing the perimeter or the area over all empty pseudo-triangles defined by P. If P lies inside a triangle whose corners must be used, we can solve these problems in O(n3) time. In the general case, the running times are O(n6) for the maximization problems and O(nlogn) for the minimization problems. 相似文献
11.
Yu. V. Matiyasevich 《Journal of Mathematical Sciences》2004,121(3):2401-2408
With an arbitrary graph G having n vertices and m edges, and with an arbitrary natural number p, we associate in a natural way a polynomial R(x
1,...,x
n) with integer coefficients such that the number of colorings of the vertices of the graph G in p colors is equal to p
m-n
R(0,...,0). Also with an arbitrary maximal planar graph G, we associate several polynomials with integer coefficients such that the number of colorings of the edges of the graph G in 3 colors can be calculated in several ways via the coefficients of each of these polynomials. Bibliography: 2 titles. 相似文献
12.
Let a connected undirected graph G = (V, E) be given. In the classical p-median problem we want to find a set X containing p points in G such that the sum of weighted distances from X to all vertices in V is minimized. We consider the semi-obnoxious case where every vertex has either a positive or negative weight. In this case
we have two different objective functions: the sum of the minimum weighted distances from X to all vertices and the sum of the weighted minimum distances. In this paper we show that for the case p = 3 an optimal solution for the second model in a tree can be found in O(n
5) time. If the 3-median is restricted to vertices or if the tree is a path then the complexity can be reduced to O(n
3).
This research has partially been supported by the Spezialforschungsbereich F 003 “Optimierung und Kontrolle”, Projektbereich
Diskrete Optimierung. 相似文献
13.
A geometric graph is a graph drawn in the plane so that the vertices are represented by points in general position, the edges are represented
by straight line segments connecting the corresponding points.
Improving a result of Pach and T?rőcsik, we show that a geometric graph on n vertices with no k+1 pairwise disjoint edges has at most k
3
(n+1) edges. On the other hand, we construct geometric graphs with n vertices and approximately (3/2)(k-1)n edges, containing no k+1 pairwise disjoint edges.
We also improve both the lower and upper bounds of Goddard, Katchalski, and Kleitman on the maximum number of edges in a
geometric graph with no four pairwise disjoint edges.
Received May 7, 1998, and in revised form March 24, 1999. 相似文献
14.
Grid Embedding of 4-Connected Plane Graphs 总被引:1,自引:0,他引:1
Xin He 《Discrete and Computational Geometry》1997,17(3):339-358
A straight line grid embedding of a plane graph G is a drawing of G such that the vertices are drawn at grid points and the edges are drawn as nonintersecting straight line segments. In this
paper we show that if a 4-connected plane graph G has at least four vertices on its external face, then G can be embedded on a grid of size such that and , where n is the number of vertices of G. Such an embedding can be computed in linear time.
Received March 30, 1995, and in revised form January 3, 1996. 相似文献
15.
Let be a family of n compact connected sets in the plane, whose intersection graph has no complete bipartite subgraph with k vertices in each of its classes. Then has at most n times a polylogarithmic number of edges, where the exponent of the logarithmic factor depends on k. In the case where consists of convex sets, we improve this bound to O(n log n). If in addition k = 2, the bound can be further improved to O(n). © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 205–214, 2008 相似文献
16.
We study the phase transition of the minimum degree multigraph process. We prove that for a constant hg ≈︁ 0.8607, with probability tending to 1 as n → ∞, the graph consists of small components on O(log n) vertices when the number of edges of a graph generated so far is smaller than hgn, the largest component has order roughly n2/3 when the number of edges added is exactly hgn, and the graph consists of one giant component on Θ(n) vertices and small components on O(log n) vertices when the number of edges added is larger than hgn. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007 相似文献
17.
Let f(n, γ) denote the largest integer r such that any graph G on n vertices with γn2 edges contains an r-regular subgraph. In this paper we prove that © 1997 John Wiley & Sons, Inc. 相似文献
18.
Eyal Ackerman 《Discrete and Computational Geometry》2009,41(3):365-375
A topological graph is called k
-quasi-planar if it does not contain k pairwise crossing edges. It is conjectured that for every fixed k, the maximum number of edges in a k-quasi-planar graph on n vertices is O(n). We provide an affirmative answer to the case k=4. 相似文献
19.
Ervin Győri 《Combinatorica》1991,11(3):231-243
In this paper, we prove that any graph ofn vertices andt
r–1(n)+m edges, wheret
r–1(n) is the Turán number, contains (1–o(1)m edge disjointK
r'sifm=o(n
2). Furthermore, we determine the maximumm such that every graph ofn vertices andt
r–1(n)+m edges containsm edge disjointK
r's ifn is sufficiently large.Research partially supported by Hungarian National Foundation for Scientific Research Grant no. 1812. 相似文献
20.
F. R. K. Chung 《Journal of Graph Theory》1981,5(1):109-113
Let r(k) denote the least integer n-such that for any graph G on n vertices either G or its complement G contains a complete graph Kk on k vertices. in this paper, we prove the following lower bound for the Ramsey number r(k) by explicit construction: r(k) ≥ exp (c(Log k)4/3[(log log k)1/3] for some constant c> 0. 相似文献