We prove crossing number inequalities for geometric graphs whose vertex sets are taken from a d-dimensional grid of volume N and give applications of these inequalities to counting the number of non-crossing geometric graphs that can be drawn on such grids. In particular, we show that any geometric graph with m >= 8N edges and with vertices on a 3D integer grid of volume N, has ((m^2 n) (m n)) crossings. In d-dimensions, with d >= 4, this bound becomes (m^2 n). We provide matching upper bounds for all d. Finally, for d >= 4 the upper bound implies that the maximum number of crossing-free geometric graphs with vertices on some d-dimensional grid of volume N is n^ (n). In 3 dimensions it remains open to improve the trivial bounds, namely, the 2^ (n) lower bound and the n^O(n) upper bound.
The work most closely related to the current work, in that it presents an extremal result relating crossings, volume, and number of edges, is that of Bose al @cite_27 , who show that the maximum number of edges in a crossing-free @math -D geometric grid graph, @math , with vertex set @math , is exactly For a fixed volume, @math , maximizing gives @math , in which case becomes @math . We state this here as lemma since we make use of it several times. boser immediately yields the upper-bound @math (see the beginning of counting ). It also yields the lower-bound @math since, if a geometric grid graph @math has @math we can remove an edge an edge from @math that eliminates at least one crossing. Since this can be repeated until @math has @math edges, this implies that @math has at least @math crossings.
@cite_27
2161190897
We present algorithmic and hardness results for network design problems with degree or order constraints. The first problem we consider is the Survivable Network Design problem with degree constraints on vertices. The objective is to find a minimum cost subgraph which satisfies connectivity requirements between vertices and also degree upper bounds @math on the vertices. This includes the well-studied Minimum Bounded Degree Spanning Tree problem as a special case. Our main result is a @math -approximation algorithm for the edge-connectivity Survivable Network Design problem with degree constraints, where the cost of the returned solution is at most twice the cost of an optimum solution (satisfying the degree bounds) and the degree of each vertex @math is at most @math . This implies the first constant factor (bicriteria) approximation algorithms for many degree constrained network design problems, including the Minimum Bounded Degree Steiner Forest problem. Our results also extend to directed graphs and provide the first constant factor (bicriteria) approximation algorithms for the Minimum Bounded Degree Arborescence problem and the Minimum Bounded Degree Strongly @math -Edge-Connected Subgraph problem. In contrast, we show that the vertex-connectivity Survivable Network Design problem with degree constraints is hard to approximate, even when the cost of every edge is zero. A striking aspect of our algorithmic result is its simplicity. It is based on the iterative relaxation method, which is an extension of Jain's iterative rounding method. This provides an elegant and unifying algorithmic framework for a broad range of network design problems. We also study the problem of finding a minimum cost @math -edge-connected subgraph with at least @math vertices, which we call the @math -subgraph problem. This generalizes some well-studied classical problems such as the @math -MST and the minimum cost @math -edge-connected subgraph problems. We give a polylogarithmic approximation for the @math -subgraph problem. However, by relating it to the Densest @math -Subgraph problem, we provide evidence that the @math -subgraph problem might be hard to approximate for arbitrary @math .