Embedding Planar Graphs at Fixed Vertex Locations

 Let G be a planar graph of n vertices, v ₁,…,v _n , and let {p ₁,…,p _n } be a set of n points in the plane. We present an algorithm for constructing in O(n ²) 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/40³ bends. Received: May 24, 1999 Final version received: April 10, 2000     

A separator theorem for graphs of bounded genus

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.     

On edges crossing few other edges in simple topological complete graphs

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 Ω(n^3/2)≤h(n)≤O(n²/log^1/4n). We also show that the analogous function on other surfaces (torus, Klein bottle) grows as cn².     

Computing Vertex Connectivity: New Bounds from Old Techniques

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{κ³ + 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(κ₁nmlog(n²/m)) where κ₁ ≤ m/n is the unweighted vertex connectivity or in expected time O(nmlog(n²/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.     

Covering minimum spanning trees of random subgraphs

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 log_bn) 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 log_bn) 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     

The book crossing number of a graph

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(log² 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(m²/k²) crossings on k pages. This is within a constant multiplicative factor from our general lower bound of Ω(m³/n²k²), provided that m = Ψ(n²). © 1996 John Wiley & Sons, Inc.     

Incremental algorithms for minimal length paths

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(n²) edge insertions and at most O(Cn²) edge cost decreases is O(Cn³ 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(n²) insertions of edges becomes O(n³ 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.     

An exact algorithm for subgraph homeomorphism

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 2^n−pn^O(1) or in time 3^n−pn^O(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.     

Untangling Polygons and Graphs

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 δ.     

Empty pseudo-triangles in point sets

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 Θ(n²) and Θ(n³) empty pseudo-triangles. If the convex vertices of the pseudo-triangle are also chosen from P, this number lies between Θ(n³) and Θ(n⁶). If we count only star-shaped pseudo-triangles, the bounds are Θ(n²) and Θ(n⁵). 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(n³) time. In the general case, the running times are O(n⁶) for the maximization problems and O(nlogn) for the minimization problems.     

Some Algebraic Methods for Calculating the Number of Colorings of a Graph

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 ₁,...,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.     

A polynomial method for the pos/neg weighted 3-median problem on a tree

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 ⁵) 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 ³). This research has partially been supported by the Spezialforschungsbereich F 003 “Optimierung und Kontrolle”, Projektbereich Diskrete Optimierung.     

Geometric Graphs with Few Disjoint Edges

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 ³ (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.     

Grid Embedding of 4-Connected Plane Graphs

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.     

On planar intersection graphs with forbidden subgraphs

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     

Phase transition of the minimum degree random multigraph process

We study the phase transition of the minimum degree multigraph process. We prove that for a constant h_g ≈︁ 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 h_gn, the largest component has order roughly n^2/3 when the number of edges added is exactly h_gn, 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 h_gn. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Note on regular subgraphs

Let f(n, γ) denote the largest integer r such that any graph G on n vertices with γn² edges contains an r-regular subgraph. In this paper we prove that © 1997 John Wiley & Sons, Inc.     

On the Maximum Number of Edges in Topological Graphs with no Four Pairwise Crossing Edges

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.     

On the number of edge disjoint cliques in graphs of given size

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 ²). 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.     

A note on constructive methods for ramsey numbers

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 K_k 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.