Linear models for the approximate solution of the problem of packing equal circles into a given domain

The linear models for the approximate solution of the problem of packing the maximum number of equal circles of the given radius into a given closed bounded domain G are proposed. We construct a grid in G; the nodes of this grid form a finite set of points T, and it is assumed that the centers of circles to be packed can be placed only at the points of T. The packing problems of equal circles with the centers at the points of T are reduced to 0–1 linear programming problems. A heuristic algorithm for solving the packing problems based on linear models is proposed. This algorithm makes it possible to solve packing problems for arbitrary connected closed bounded domains independently of their shape in a unified manner. Numerical results demonstrating the effectiveness of this approach are presented.     

Extending immersions of curves to properly immersed surfaces

Proper generic immersions of compact one-dimensional manifolds in surfaces are studied. Suppose an immersion γ of a collection of circles is given with an even number of double points in a closed surface G. Then γ extends to various proper immersions of surfaces in three-manifolds that are bounded by G. Some of these extensions do not have triple points. The minimum of the genera of the triple point free surfaces is an invariant of the curve. An algorithm to compute this invariant is given.Necessary and suffecient conditions determine if a given collection δ of immersed arcs in a surface F maps to the double points set of a proper immersion. In case the conditions are satisfied, an immersion of F into a three-manifold that depends on δ is constructed explicitly. In the process, the possible triple points of immersed surfaces in three-manifolds are categorized.The techniques are applied to find examples of curves in surfaces that do not bound immersed disks in any three-manifold.     

Approximation of conformal mappings by circle patterns

A circle pattern is a configuration of circles in the plane whose combinatorics is given by a planar graph G such that to each vertex of G corresponds a circle. If two vertices are connected by an edge in G, the corresponding circles intersect with an intersection angle in (0, π). Two sequences of circle patterns are employed to approximate a given conformal map g and its first derivative. For the domain of g we use embedded circle patterns where all circles have the same radius decreasing to 0 and with uniformly bounded intersection angles. The image circle pattern has the same combinatorics and intersection angles and is determined from boundary conditions (radii or angles) according to the values of g′ (|g′| or arg g′). For quasicrystallic circle patterns the convergence result is strengthened to C ^∞-convergence on compact subsets.      

The Ulam number of infinite graphs

The following is a conjecture of Ulam: In any partition of the integer lattice on the plane into uniformly bounded sets, there exists a set that is adjacent to at least six other sets. Two sets are adjacent if each contain a vertex of the same unit square. This problem is generalized as follows. Given any uniformly bounded partitionP of the vertex set of an infinite graphG with finite maximum degree, letP (G) denote the graph obtained by letting each set of the partition be a vertex ofP (G) where two vertices ofP (G) are adjacent if and only if the corresponding sets have an edge between them. The Ulam number ofG is defined as the minimum of the maximum degree ofP (G) where the minimum is taken over all uniformly bounded partitionsP. We have characterized the graphs with Ulam number 0, 1, and 2. Restricting the partitions of the vertex set to connected subsets, we obtain the connected Ulam number ofG. We have evaluated the connected Ulam numbers for several infinite graphs. For instance we have shown that the connected Ulam number is 4 ifG is an infinite grid graph. We have settled the Ulam conjecture for the connected case by proving that the connected Ulam number is 6 for an infinite triangular grid graph. The general Ulam conjecture is equivalent to proving that the Ulam number of the infinite triangular grid graph equals 6. We also describe some interesting geometric consequences of the Ulam number, mainly concerning good drawings of infinite graphs.     

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.     

Packing up to 50 Equal Circles in a Square

The problem of maximizing the radius of n equal circles that can be packed into a given square is a well-known geometrical problem. An equivalent problem is to find the largest distance d, such that n points can be placed into the square with all mutual distances at least d. Recently, all optimal packings of at most 20 circles in a square were exactly determined. In this paper, computational methods to find good packings of more than 20 circles are discussed. The best packings found with up to 50 circles are displayed. A new packing of 49 circles settles the proof that when n is a square number, the best packing is the square lattice exactly when n≤ 36. Received April 24, 1995, and in revised form June 14, 1995.     

Inclusion functions and global optimization II

This paper discusses algorithms of Moore, Skelboe, Ichida, Fujii and Hansen for solving the global unconstrained optimization problem. These algorithms have been tried on computers, but a thorough theoretical discussion of their convergence properties has been missing. The discussion was started in part I of this paper (Mathematical Programming 33 (1985) 300–317) where the convergence to the global minimum was studied. The present paper is concerned with the different behaviours of these algorithms when they are used for the determination of global minimum points. The solution sets of the algorithms can be a subset of the set of global minimum points,G, a superset ofG, or exactlyG. The algorithms are applicable to a very general class of functions: functions which are continuous, and have suitable inclusion functions. The number of global minimum points can be infinite.This work was supported by the Deutsche Forschungsgemeinschaft.     

Approximating the Minimum-Degree Steiner Tree to within One of Optimal

The problem of constructing a spanning tree for a graph G = (V, E) with n vertices whose maximal degree is the smallest among all spanning trees of G is considered. This problem is easily shown to be NP-hard. In the Steiner version of this problem, along with the input graph, a set of distinguished vertices D V is given. A minimum-degree Steiner tree is a tree of minimum degree which spans at least the set D. Iterative polynomial time approximation algorithms for the problems are given. The algorithms compute trees whose maximal degree is at most Δ* + 1, where Δ* is the degree of some optimal tree for the respective problems. Unless P = NP, this is the best bound achievable in polynomial time.     

Numerical optimization method for packing regular convex polygons

An algorithm is presented for the approximate solution of the problem of packing regular convex polygons in a given closed bounded domain G so as to maximize the total area of the packed figures. On G a grid is constructed whose nodes generate a finite set W on G, and the centers of the figures to be packed can be placed only at some points of W. The problem of packing these figures with centers in W is reduced to a 0-1 linear programming problem. A two-stage algorithm for solving the resulting problems is proposed. The algorithm finds packings of the indicated figures in an arbitrary closed bounded domain on the plane. Numerical results are presented that demonstrate the effectiveness of the method.     

On vertex k-partitions of certain infinite graphs

Let G be an infinite graph; define deg∞ G to be the least m such that any partition P of the vertex set of G into sets of uniformly bounded cardinality contains a set which is adjacent to at least m other sets of the partition. If G is either a regular tree on a triangular, square or hexagonal planar mosaic graph, it is shown that deg∞ G equals the degree of G. This verifies some conjectures of S. Ulam. Several open problems are given.     

Fast state space algorithms for matrix Nehari and Nehari-Takagi interpolation problems

Numerical algorithms with complexityO(n ²) operations are proposed for solving matrix Nehari and Nehari-Takagi problems withn interpolation points. The algorithms are based on explicit formulas for the solutions and on theorems about cascade decomposition of rational matrix function given in a state space form. The method suggests also fast algorithms for LDU factorizations of structured matrices. The numerical behavior of the designed algorithms is studied for a wide set of examples.     

Packing congruent hyperspheres into a hypersphere

The paper considers a problem of packing the maximal number of congruent nD hyperspheres of given radius into a larger nD hypersphere of given radius where n = 2, 3, . . . , 24. Solving the problem is reduced to solving a sequence of packing subproblems provided that radii of hyperspheres are variable. Mathematical models of the subproblems are constructed. Characteristics of the mathematical models are investigated. On the ground of the characteristics we offer a solution approach. For n ≤ 3 starting points are generated either in accordance with the lattice packing of circles and spheres or in a random way. For n > 3 starting points are generated in a random way. A procedure of perturbation of lattice packings is applied to improve convergence. We use the Zoutendijk feasible direction method to search for local maxima of the subproblems. To compute an approximation to a global maximum of the problem we realize a non-exhaustive search of local maxima. Our results are compared with the benchmark results for n = 2. A number of numerical results for 2 ≤ n ≤ 24 are given.     

Connected Domatic Number in Planar Graphs

A dominating set in a graph G is a connected dominating set of G if it induces a connected subgraph of G. The connected domatic number of G is the maximum number of pairwise disjoint, connected dominating sets in V(G). We establish a sharp lower bound on the number of edges in a connected graph with a given order and given connected domatic number. We also show that a planar graph has connected domatic number at most 4 and give a characterization of planar graphs having connected domatic number 3.     

A generalization of a theorem by Bigard–Keimel and Conrad–Diem

Let G be an archimedean ℓ-group and \mathfrakP(G){\mathfrak{P}(G)} denote the set of all polar preserving bounded group endomorphisms of G. Bigard and Keimel in [Bull. Soc. Math. France 97 (1969), 381–398] and, independently, Conrad and Diem in [Illinois J. Math. 15 (1971), 222–240] proved that \mathfrakP(G){\mathfrak{P}(G)} is an archimedean ℓ-group with respect to the pointwise addition and ordering. This classical result is extended in this paper to certain sets of disjointness preserving bounded homomorphisms on archimedean ℓ-groups.     

UPPER BOUNDS ON THE LOWER OPEN PACKING NUMBER OF A TREE

Abstract

Let G be a graph and let v be a vertex of G. The open neigbourhood N(v) of v is the set of all vertices adjacent with v in G. An open packing of G is a set of vertices whose open neighbourhoods are pairwise disjoint. The lower open packing number of G, denoted ρ^° _L(G), is the minimum cardinality of a maximal open packing of G while the (upper) open packing number of G, denoted ρ^°(G), is the maximum cardinality among all open packings of G. It is known (see [7]) that if G is a connected graph of order n ≥3, then ρ^°(G) ≤ 2n/3 and this bound is sharp (even for trees). As a consequence of this result, we know that ρ^° _L(G) ≤ 2n/3. In this paper, we improve this bound when G is a tree. We show that if G is a tree of order n with radius 3, then ρ^° _L(G) ≤ n/2 + 2 √n-1, and this bound is sharp, while if G is a tree of order n with radius at least 4, then ρ^° _L(G) is bounded above by 2n/3—O√n).     

On the Acyclic Chromatic Number of Hamming Graphs

An acyclic coloring of a graph G is a proper coloring of the vertex set of G such that G contains no bichromatic cycles. The acyclic chromatic number of a graph G is the minimum number k such that G has an acyclic coloring with k colors. In this paper, acyclic colorings of Hamming graphs, products of complete graphs, are considered. Upper and lower bounds on the acyclic chromatic number of Hamming graphs are given. Gretchen L. Matthews: The work of this author is supported by NSA H-98230-06-1-0008.     

Relative Chebyshev centers in normed linear spaces, part II

Let E be a normed linear space, A a bounded set in E, and G an arbitrary set in E. The relative Chebyshev center of A in G is the set of points in G best approximating A. We have obtained elsewhere general results characterizing the spaces in which the center reduces to a singleton in terms of structural properties related to uniform and strict convexity. In this paper, an analysis of the Chebyshev norm case, which falls outside the scope of the previous analysis, is presented.     

Some finiteness results for groups with bounded algebraic entropy

We prove that the number of elements of any generating set S of a discrete group G is bounded from above if we assume that the algebraic entropy of G with respect to S is smaller than some universal constant and the existence of a finite index subgroup of G with hyperbolicity properties. We deduce some finiteness results for the pairs (G, S) when G is a word-hyperbolic group or the fundamental group of a compact Riemannian manifold.     

Algorithms for finding distance-edge-colorings of graphs

For a bounded integer ℓ, we wish to color all edges of a graph G so that any two edges within distance ℓ have different colors. Such a coloring is called a distance-edge-coloring or an ℓ-edge-coloring of G. The distance-edge-coloring problem is to compute the minimum number of colors required for a distance-edge-coloring of a given graph G. A partial k-tree is a graph with tree-width bounded by a fixed constant k. We first present a polynomial-time exact algorithm to solve the problem for partial k-trees, and then give a polynomial-time 2-approximation algorithm for planar graphs.     

Variable neighborhood search for extremal graphs. 21. Conjectures and results about the independence number

A set of vertices S in a graph G is independent if no neighbor of a vertex of S belongs to S. The independence number α is the maximum cardinality of an independent set of G. A series of best possible lower and upper bounds on α and some other common invariants of G are obtained by the system AGX 2, and proved either automatically or by hand. In the present paper, we report on such lower and upper bounds considering, as second invariant, minimum, average and maximum degree, diameter, radius, average distance, spread of eccentricities, chromatic number and matching number.