On the Chromatic Number of Subsets of the Euclidean Plane

The chromatic number of a subset of the real plane is the smallest number of colors assigned to the elements of that set such that no two points at distance 1 receive the same color. It is known that the chromatic number of the plane is at least 4 and at most 7. In this note, we determine the bounds on the chromatic number for several classes of subsets of the plane such as extensions of the rational plane, sets in convex position, infinite strips, and parallel lines.     

Coloring arcs of convex sets

In this note we consider Ramsey-type problems on graphs whose vertices are represented by the vertices of a convex polygon in the Euclidean plane. The edges of the graph are represented by the segments between the points of the polygon. The edges are arbitrarily colored by a fixed number of colors and the problem is to decide whether there exist monochromatic subgraphs of certain types satisfying some geometric conditions. We will give lower and upper bounds for these geometric Ramsey numbers for certain paths and cycles and also some exact values. It turns out that the particular type of the embedding is crucial for the growth rate of the corresponding geometric Ramsey numbers. In particular, the Ramsey numbers for crossing 4-cycles and t colors grow quadratically in t, while for convex 4-cycles they grow at least exponentially.     

EDGE-FACE CHROMATIC NUMBER OF 2-CONNECTED PLANE GRAPHS WITH HIGH MAXIMUM DEGREE

The edge-face chromatic number Xef (G) of a plane graph G is the least number of colors assigned to the edges and faces such that every adjacent or incident pair of them receives different colors. In this article, the authors prove that every 2-connected plane graph G with△(G)≥|G| -2△9 has Xef(G)=△(G).     

Geometric Achromatic and Pseudoachromatic Indices

The pseudoachromatic index of a graph is the maximum number of colors that can be assigned to its edges, such that each pair of different colors is incident to a common vertex. If for each vertex its incident edges have different color, then this maximum is known as achromatic index. Both indices have been widely studied. A geometric graph is a graph drawn in the plane such that its vertices are points in general position, and its edges are straight-line segments. In this paper we extend the notion of pseudoachromatic and achromatic indices for geometric graphs, and present results for complete geometric graphs. In particular, we show that for n points in convex position the achromatic index and the pseudoachromatic index of the complete geometric graph are \(\lfloor \frac{n^2+n}{4} \rfloor \).     

On the expected number of optimal and near-optimal solutions to the Euclidean travelling salesman problem

An algorithm for empirically calculating the expected number of optimal and near-optimal solutions in a random Euclidean travelling salesman problem is presented. The algorithm is based on well known geometric properties of the optimal tour. For problems involving up to 15 points uniformily distributed in the unit square, experiments show this expected number to be extremely small.     

Internal Twists of <Emphasis Type="Italic">L</Emphasis>-Functions. II

The Capacitated Vehicle Routing Problem (CVRP) is a classic combinatorial optimization problem with a wide range of applications in operations research. Since the CVRP is NP-hard even in a finite-dimensional Euclidean space, special attention is traditionally paid to the issues of its approximability. A major part of the known results concerning approximation algorithms and polynomial-time approximation schemes (PTAS) for this problem are obtained for its particular statement in the Euclidean plane. In this paper, we show that the approach to the development of a PTAS for the planar problem with a single depot proposed by Haimovich and Rinnooy Kan in 1985 can be successfully extended to the more general case, for instance, in spaces of arbitrary fixed dimension and for an arbitrary number of depots.     

The fixed point property and unbounded sets in CAT(0) spaces

In this work we study the fixed point property for nonexpansive self-mappings defined on convex and closed subsets of a CAT(0) space. We will show that a positive answer to this problem is very much linked with the Euclidean geometry of the space while the answer is more likely to be negative if the space is more hyperbolic. As a consequence we extend a very well known result of W.O. Ray on Hilbert spaces.     

Edge-Colorings of 4-Regular Graphs with the Minimum Number of Palettes

A proper edge-coloring of a graph G is an assignment of colors to the edges of G such that adjacent edges receive distinct colors. A proper edge-coloring defines at each vertex the set of colors of its incident edges. Following the terminology introduced by Horňák, Kalinowski, Meszka and Wo?niak, we call such a set of colors the palette of the vertex. What is the minimum number of distinct palettes taken over all proper edge-colorings of G? A complete answer is known for complete graphs and cubic graphs. We study in some detail the problem for 4-regular graphs. In particular, we show that certain values of the palette index imply the existence of an even cycle decomposition of size 3 (a partition of the edge-set of a graph into 3 2-regular subgraphs whose connected components are cycles of even length). This result can be extended to 4d-regular graphs. Moreover, in studying the palette index of a 4-regular graph, the following problem arises: does there exist a 4-regular graph whose even cycle decompositions cannot have size smaller than 4?     

A Schwarz Lemma for Harmonic Mappings Between the Unit Balls in Real Euclidean Spaces

The authors prove a Schwarz lemma for harmonic mappings between the unit balls in real Euclidean spaces. Roughly speaking, this result says that under a harmonic mapping between the unit balls in real Euclidean spaces, the image of a smaller ball centered at origin can be controlled. This extends the related result proved by Chen in complex plane.     

On the Helly Number for Hyperplane Transversals to Unit Balls

We prove two results about the Hadwiger problem of finding the Helly number for line transversals of disjoint unit disks in the plane, and about its higher-dimensional generalization to hyperplane transversals of unit balls in d -dimensional Euclidean space. These consist of (a) a proof of the fact that the Helly number remains 5 even for arbitrarily large sets of disjoint unit disks—thus correcting a 40-year-old error; and (b) a lower bound of d+3 on the Helly number for hyperplane transversals to suitably separated families of unit balls in R ^d . Received January 25, 1999, and in revised form July 7, 1999.     

Minimum Networks for Four Points in Space

The minimum network problem (Steiner tree problem) in space is much harder than the one in the Euclidean plane. The Steiner tree problem for four points in the plane has been well studied. In contrast, very few results are known on this simple Steiner problem in 3D-space. In the first part of this paper we analyze the difficulties of the Steiner problem in space. From this analysis we introduce a new concept — Simpson intersections, and derive a system of iteration formulae for computing Simpson intersections. Using Simpson intersections the Steiner points can be determined by solving quadratic equations. As well this new computational method makes it easy to check the impossibility of computing Steiner trees on 4-point sets by radicals. At the end of the first part we consider some special cases (planar and symmetric 3D-cases) that can be solved by radicals. The Steiner ratio problem is to find the minimum ratio of the length of a Steiner minimal tree to the length of a minimal spanning tree. This ratio problem in the Euclidean plane was solved by D. Z. Du and F. K. Hwang in 1990, but the problem in 3D-space is still open. In 1995 W.D. Smith and J.M. Smith conjectured that the Steiner ratio for 4-point sets in 3D-space is achieved by regular tetrahedra. In the second part of this paper, using the variational method, we give a proof of this conjecture.     

Plane Embeddings of Planar Graph Metrics

Embedding metrics into constant-dimensional geometric spaces, such as the Euclidean plane, is relatively poorly understood. Motivated by applications in visualization, ad-hoc networks, and molecular reconstruction, we consider the natural problem of embedding shortest-path metrics of unweighted planar graphs (planar graph metrics) into the Euclidean plane. It is known that, in the special case of shortest-path metrics of trees, embedding into the plane requires distortion in the worst case [M1], [BMMV], and surprisingly, this worst-case upper bound provides the best known approximation algorithm for minimizing distortion. We answer an open question posed in this work and highlighted by Matousek [M3] by proving that some planar graph metrics require distortion in any embedding into the plane, proving the first separation between these two types of graph metrics. We also prove that some planar graph metrics require distortion in any crossing-free straight-line embedding into the plane, suggesting a separation between low-distortion plane embedding and the well-studied notion of crossing-free straight-line planar drawings. Finally, on the upper-bound side, we prove that all outerplanar graph metrics can be embedded into the plane with distortion, generalizing the previous results on trees (both the worst-case bound and the approximation algorithm) and building techniques for handling cycles in plane embeddings of graph metrics.     

Minimum sum edge colorings of multicycles

In the minimum sum edge coloring problem, we aim to assign natural numbers to edges of a graph, so that adjacent edges receive different numbers, and the sum of the numbers assigned to the edges is minimum. The chromatic edge strength of a graph is the minimum number of colors required in a minimum sum edge coloring of this graph. We study the case of multicycles, defined as cycles with parallel edges, and give a closed-form expression for the chromatic edge strength of a multicycle, thereby extending a theorem due to Berge. It is shown that the minimum sum can be achieved with a number of colors equal to the chromatic index. We also propose simple algorithms for finding a minimum sum edge coloring of a multicycle. Finally, these results are generalized to a large family of minimum cost coloring problems.     

Plane graphs of maximum degree Δ ≥ 7 are edge-face (Δ + 1)-colorable

A plane graph G is edge-face k-colorable if its edges and faces can be colored with k colors such that any two adjacent or incident elements receive different colors. It is known that every plane graph G of maximum degree Δ ≥ 8 is edge-face (Δ + 1)-colorable. The condition Δ ≥ 8 is improved to Δ ≥ 7 in this paper.     

Dynamic task assignment for throughput maximization with worksharing

The traditional assembly line balancing problem involves assigning a set of partially precedence constrained tasks to workstations to maximize efficiency. Each task is assigned to a unique workstation. The case is considered where task sequences are known but the workforce is partially cross-trained and some tasks can alternate between workstations. The flexibility afforded by cross-training allows the line balance to improve. Task times are allowed to be random and small buffers are allowed between workstations. Decision rules are developed and tested for various levels of cross-training between adjacent workers. Cross-training is shown to have significant impact on throughput and easy to administer rules are proven to be effective. The number of decision points for deciding to hold or pass a unit of product is also shown to be important.     

A reduction of lattice tiling by translates of a cubical cluster

A cluster is the union of a finite number of cubes from the standard partition ofn-dimensional Euclidean space into unit cubes. If there is lattice tiling by translates of a cluster, then must there be a lattice tiling by translates of the cluster in which the translation vectors have only integer coordinates? In this article we prove that if the interior of the cluster is connected and the dimension is at most three, then the answer is affirmative.     

The plane‐width of graphs

Map the vertices of a graph to (not necessarily distinct) points of the plane so that two adjacent vertices are mapped at least unit distance apart. The plane‐width of a graph is the minimum diameter of the image of its vertex set over all such mappings. We establish a relation between the plane‐width of a graph and its chromatic number. We also connect it to other well‐known areas, including the circular chromatic number and the problem of packing unit discs in the plane. © 2011 Wiley Periodicals, Inc. J Graph Theory 68: 229‐245, 2011     

一类一维在线单位聚类问题的随机近似算法

在给定的度量空间中, 单位聚类问题就是寻找最少的单位球来覆盖给定的所有点。这是一个众所周知的组合优化问题, 其在线版本为: 给定一个度量空间, 其中的n个点会一个接一个的到达任何可能的位置, 在点到达的时候必须给该点分配一个单位聚类, 而此时未来点的相关信息都是未知的, 问题的目标是最后使用的单位聚类数目最少。本文考虑的是带如下假设的一类一维在线单位聚类问题: 在相应离线问题的最优解中任意两个相邻聚类之间的距离都大于0.5。本文首先给出了两个在线算法和一些引理, 接着通过0.5的概率分别运行两个在线算法得到一个组合随机算法, 最后证明了这个组合随机算法的期望竞争比不超过1.5。     

一类一维在线单位聚类问题的随机近似算法

在给定的度量空间中, 单位聚类问题就是寻找最少的单位球来覆盖给定的所有点。这是一个众所周知的组合优化问题, 其在线版本为: 给定一个度量空间, 其中的n个点会一个接一个的到达任何可能的位置, 在点到达的时候必须给该点分配一个单位聚类, 而此时未来点的相关信息都是未知的, 问题的目标是最后使用的单位聚类数目最少。本文考虑的是带如下假设的一类一维在线单位聚类问题: 在相应离线问题的最优解中任意两个相邻聚类之间的距离都大于0.5。本文首先给出了两个在线算法和一些引理, 接着通过0.5的概率分别运行两个在线算法得到一个组合随机算法, 最后证明了这个组合随机算法的期望竞争比不超过1.5。     

Approximating geometric bottleneck shortest paths

In a geometric bottleneck shortest path problem, we are given a set S of n points in the plane, and want to answer queries of the following type: given two points p and q of S and a real number L, compute (or approximate) a shortest path between p and q in the subgraph of the complete graph on S consisting of all edges whose lengths are less than or equal to L. We present efficient algorithms for answering several query problems of this type. Our solutions are based on Euclidean minimum spanning trees, spanners, and the Delaunay triangulation. A result of independent interest is the following. For any two points p and q of S, there is a path between p and q in the Delaunay triangulation, whose length is less than or equal to 2π/(3cos(π/6)) times the Euclidean distance |pq| between p and q, and all of whose edges have length at most |pq|.