Finding intersection of rectangles by range search

Three related rectangle intersection problems in k-dimensional space are considered: (1) find the intersections of a rectangle with a given set of rectangles, (2) find the intersecting pairs of rectangles as they are inserted into or deleted from an existing set of rectangles, and (3) find the intersecting pairs of a given set of rectangles. By transforming these problems into range search problems, one need not divide the intersection problem into two subproblems, namely, the edge-intersecting problem and the containment problem, as done by many previous studies. Furthermore, this approach can also solve these subproblems separately, if required. For the first problem the running time is O((log n)^2k−1 + s), where s is the number of intersecting pairs of rectangles. For the second problem the time needed to generate and maintain n rectangles is O(n(log n)^2k) and the time for each query is O((log n)^2k−1 + s). For the third problem the total time is O(n log n + n(log n)^2(k−1) + s) for k ≥ 1.     

Computing the maximum clique in the visibility graph of a simple polygon

In this paper, we present an algorithm for computing the maximum clique in the visibility graph G of a simple polygon P in O(n²e) time, where n and e are number of vertices and edges of G respectively. We also present an O(ne) time algorithm for computing the maximum hidden vertex set in the visibility graph G of a convex fan P. We assume in both algorithms that the Hamiltonian cycle in G that corresponds to the boundary of P is given as an input along with G.     

The entire graph of a bridgeless connected plane graph is hamiltonian

In this paper we show that the entire graph of a bridgeless connected plane graph is hamiltonian, and that the entire graph of a plane block is hamiltonian connected and vertex pancyclic. In addition, we show that in any block G which is not a circuit, given a vertex v of G and a circuit k of G, there is a path p, suspended in G, such that p is a path in k of length at least 1 and G ? E(p) ? V₀(G ? E(p)) is a block which includes v.     

Exploring the constrained maximum edge-weight connected graph problem

Given an edge weighted graph, the maximum edge-weight connected graph （MECG） is a connected subgraph with a given number of edges and the maximal weight sum. Here we study a special case, i.e. the Constrained Maximum Edge-Weight Connected Graph problem （CMECG）, which is an MECG whose candidate subgraphs must include a given set of k edges, then also called the k-CMECG. We formulate the k-CMECG into an integer linear programming model based on the network flow problem. The k-CMECG is proved to be NP-hard. For the special case 1-CMECG, we propose an exact algorithm and a heuristic algorithm respectively. We also propose a heuristic algorithm for the k-CMECG problem. Some simulations have been done to analyze the quality of these algorithms. Moreover, we show that the algorithm for 1-CMECG problem can lead to the solution of the general MECG problem.     

On the largest tree of given maximum degree in a connected graph

We prove that every connected graph G contains a tree T of maximum degree at most k that either spans G or has order at least kδ(G) + 1, where δ(G) is the minimum degree of G. This generalizes and unifies earlier results of Bermond [1] and Win [7]. We also show that the square of a connected graph contains a spanning tree of maximum degree at most three.     

Finding connected components of a semialgebraic set in subexponential time

Let a semialgebraic set be defined by a quantifier-free formula with atomic subformulas of the form f_i>0, 0,1 i where the polynomials f_i[X₁,..., X_n] of degree deg (f_i)<d have absolute value of the coefficients at most 2^M. An algorithm is constructed which finds the connected components of the semialgebraic set (i.e., giving formulas for them) in a time that is polynomial inM (kd) ^ro(1). Collins' previously known method has a bound which is polynomial inM (kd) ^ro(1).Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 192, pp. 3–46, 1991.     

Contractibility and the clique graph operator

To any graph G we can associate a simplicial complex Δ(G) whose simplices are the complete subgraphs of G, and thus we say that G is contractible whenever Δ(G) is so. We study the relationship between contractibility and K-nullity of G, where G is called K-null if some iterated clique graph of G is trivial. We show that there are contractible graphs which are not K-null, and that any graph whose clique graph is a cone is contractible.     

The greedy clique decomposition of a graph

We prove that if maximal cliques are removed one by one from any graph with n vertices, then the graph will be empty after at most n²/4 steps. This proves a conjecture of Winkler.     

Lower bounds for the clique and the chromatic numbers of a graph

G is any simple graph with m edges and n vertices where these vertices have vertex degrees d(1)≥d(2)≥?≥d(n), respectively. General algorithms for the exact calculation of χ(G), the chromatic number of G, are almost always of ‘branch and bound’ type; this type of algorithm requires an easily constructed lower bound for χ(G). In this paper it is shown that, for a number of such bounds (many of which are described here for the first time), the bound does not exceed cl(G) where cl(G) is the clique number of G.In 1972 Myers and Liu showed that cl(G)≥n?(n?2m?n). Here we show that cl(G)≥ n?[n?(2m?n)(1+c²_v)^{$\text{1}\text{2}$}], where c_v is the vertex degree coefficient of variation in G, that cl(G)≥ Bondy's constructive lower bound for χ(G), and that cl(G)≥n?(n?W(G)), where W(G) is the largest positive integer such that W(G)≤d(W(G)+1) [W(G)+1 is the Welsh and Powell upper bound for χ(G)]. It is also shown that cl(G)+$\text{1}\text{3}$>n?(n?L(G))≥n?(n?λ₁) and that χ(G)≥ n?(n?λ₁); λ₁ is the largest eigenvalue of A, the adjacency matrix of G, and L(G) is a newly defined single-valued function of G similar to W(G) in its construction from the vertex degree sequence of G [L(G)≥W(G)].Finally, a ‘greedy’ lower bound for cl(G) is constructed from A and it is shown that this lower bound is never less than Bondy's bound; thereafter, for 150 random graphs with varying numbers of vertices and edge densities, the values of lower bounds given in this paper are listed, thereby illustrating that this last greedily obtained lower bound is almost always better than each of the other bounds.     

A characterization of intersection graphs of the maximal rectangles of a polyomino

The interior of an orthogonal polygon drawn on a regular grid of the plane defines a set of cells (or squares) called a polyomino. We prove that the intersection graph of the maximal rectangles contained in a polyomino is slightly triangulated or has a star cutset.     

On the intersection graph of a finite group

For a finite group G, the intersection graph of G which is denoted by Γ(G) is an undirected graph such that its vertices are all nontrivial proper subgroups of G and two distinct vertices H and K are adjacent when H ∩ K ≠ 1. In this paper we classify all finite groups whose intersection graphs are regular. Also, we find some results on the intersection graphs of simple groups and finally we study the structure of Aut(Γ(G)).     

An upper bound on the size of a largest clique in a graph

A graph is point determining if distinct vertices have distinct neighborhoods. The nucleus of a point-determining graph is the set G^O of all vertices, v, such that G–v is point determining. In this paper we show that the size, ω(G), of a maximum clique in G satisfies ω(G) ? 2|π (G)^O|, where π(G) (the point determinant of G) is obtained from G by identifying vertices which have the same neighborhood.     

The maximum clique and the signless Laplacian eigenvalues

Lower and upper bounds are obtained for the clique number ω(G) and the independence number α(G), in terms of the eigenvalues of the signless Laplacian matrix of a graph G. This work was supported by the National Natural Science Foundation of China (No. 10771080), SRFDP of China (No. 20070574006) and by the Foundation to the Educational Committee of Fujian (No. JB07020).     

Solving the maximum clique problem using a tabu search approach

We describe two variants of a tabu search heuristic, a deterministic one and a probabilistic one, for the maximum clique problem. This heuristic may be viewed as a natural alternative implementation of tabu search for this problem when compared to existing ones. We also present a new random graph generator, the -generator, which produces graphs with larger clique sizes than comparable ones obtained by classical random graph generating techniques. Computational results on a large set of test problems randomly generated with this new generator are reported and compared with those of other approximate methods.The authors are grateful to the Quebec Government (Fonds F.C.A.R.) and to the Canadian Natural Sciences and Engineering Research Council (grant 0GP0038816) for financial support.