On k-planar crossing numbers

The k-planar crossing number of a graph is the minimum number of crossings of its edges over all possible drawings of the graph in k planes. We propose algorithms and methods for k-planar drawings of general graphs together with lower bound techniques. We give exact results for the k-planar crossing number of K_2k+1,q, for k?2. We prove tight bounds for complete graphs. We also study the rectilinear k-planar crossing number.     

On the parity of crossing numbers

For an integer n ? 1, a graph G has an n-constant crossing number if, for any two good drawings ? and ?′ of G in the plane, μ(?) ≡ μ(?′) (mod n), where μ(?) is the number of crossings in ?. We prove that, except for trivial cases, a graph G has n-constant crossing number if and only if n = 2 and G is either K_p or K_q,r, where p, q, and r are odd.     

On crossing numbers of geometric proximity graphs

Let P be a set of n points in the plane. A geometric proximity graph on P is a graph where two points are connected by a straight-line segment if they satisfy some prescribed proximity rule. We consider four classes of higher order proximity graphs, namely, the k-nearest neighbor graph, the k-relative neighborhood graph, the k-Gabriel graph and the k-Delaunay graph. For k=0 (k=1 in the case of the k-nearest neighbor graph) these graphs are plane, but for higher values of k in general they contain crossings. In this paper, we provide lower and upper bounds on their minimum and maximum number of crossings. We give general bounds and we also study particular cases that are especially interesting from the viewpoint of applications. These cases include the 1-Delaunay graph and the k-nearest neighbor graph for small values of k.     

Biplanar crossing numbers. II. Comparing crossing numbers and biplanar crossing numbers using the probabilistic method

The biplanar crossing number cr₂(G) of a graph G is min{cr(G₁) + cr(G₂)}, where cr is the planar crossing number. We show that cr₂(G) ≤ (3/8)cr(G). Using this result recursively, we bound the thickness by Θ(G) ‐ 2 ≤ Kcr₂(G)^0.4057 log₂n with some constant K. A partition realizing this bound for the thickness can be obtained by a polynomial time randomized algorithm. We show that for any size exceeding a certain threshold, there exists a graph G of this size, which simultaneously has the following properties: cr(G) is roughly as large as it can be for any graph of that size, and cr₂(G) is as small as it can be for any graph of that size. The existence is shown using the probabilistic method. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

On the crossing numbers of Cartesian products with trees

Zip product was recently used in a note establishing the crossing number of the Cartesian product K₁,n □ P_m. In this article, we further investigate the relations of this graph operation with the crossing numbers of graphs. First, we use a refining of the embedding method bound for crossing numbers to weaken the connectivity condition under which the crossing number is additive for the zip product. Next, we deduce a general theorem for bounding the crossing numbers of (capped) Cartesian product of graphs with trees, which yields exact results under certain symmetry conditions. We apply this theorem to obtain exact and approximate results on crossing numbers of Cartesian product of various graphs with trees. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 287–300, 2007     

On crossing numbers of hypercubes and cube connected cycles

We prove tight bounds for crossing numbers of hypercube and cube connected cycles (CCC) graphs.The research of both authors was supported by Alexander von Humboldt Foundation, Bonn, Germany.     

W6*Sn的交叉数

早在20世纪50年代,Zarankiewicz 猜想完全2-部图K_{m,n}(m\leq n)的交叉数为\lfloor\frac{m}{2}\rfloor\times \lfloor\frac{m-1}{2}\rfloor\times\lfloor\frac{n}{2}\rfloor\times\lfloor\frac{n-1}{2}\rfloor (对任意实数x,\lfloor x\rfloor表示不超过x的最大整数). 目前这一猜想的正确性只证明了当m\leq6时成立. 假定著名的Zarankiewicz的猜想对m=7的情形成立,确定了6-轮W_{6}与星S_{n}的笛卡尔积图的交叉是 cr(W_{6}\times S_{n})=9\lfloor\frac{n}{2}\rfloor\times\lfloor\frac{n-1}{2}\rfloor+2n+5\lfloor\frac{n}{2}\rfloor.     

Bounds for rectilinear crossing numbers

A rectilinear drawing of a graph is one where each edge is drawn as a straight-line segment, and the rectilinear crossing number of a graph is the minimum number of crossings over all rectilinear drawings. We describe, for every integer k ≥ 4, a class of graphs of crossing number k, but unbounded rectilinear crossing number. This is best possible since the rectilinear crossing number is equal to the crossing number whenever the latter is at most 3. Further, if we consider drawings where each edge is drawn as a polygonal line segment with at most one break point, then the resulting crossing number is at most quadratic in the regular crossing number. © 1993 John Wiley & Sons, Inc.     

The bondage numbers of graphs with small crossing numbers

The bondage number b(G) of a nonempty graph G is the cardinality of a smallest edge set whose removal from G results in a graph with domination number greater than the domination number γ(G) of G. Kang and Yuan proved b(G)?8 for every connected planar graph G. Fischermann, Rautenbach and Volkmann obtained some further results for connected planar graphs. In this paper, we generalize their results to connected graphs with small crossing numbers.     

An infinite family of octahedral crossing numbers

This paper calculates some crossing numbers for certain octahedral graphs. Precisely, if the number p is a prime power congruent to 1 modulo 4, then the crossing number of the p-dimensional octahedral graph in the orientable surface of genus (p–1)(p-4)/4 is (p²–p)/2. The key step is the construction of a self-dual imbedding of the complete graph on p vertices such that no face boundary contains a repeated vertex.     

On the crossing numbers of products of cycles and graphs of order four

The main results are that the crossing number of the product C₄ × C_n is 2n for n ≥ 4 and that of the product K₄ × C_n is 3_n for n ≥ 3. These are extensions of an earlier result giving the crossing number of C₃ × C_n as n for n ≥ 3.     

Two recursive inequalities for crossing numbers of graphs

In this paper, two recursive inequalities for crossing numbers of graphs are given by using basic counting method. As their applications, the crossing numbers of K _1,3,n and K _4,n \ e are determined, respectively.     

New results on rectilinear crossing numbers and plane embeddings

We show that if a graph has maximum degree d and crossing number k, its rectilinear crossing number is at most O(dk²). Hence for graphs of bounded degree, the crossing number and the rectilinear crossing number are bounded as functions of one another. We also obtain a generalization of Tutte's theorem on convex embeddings of 3-connected plane graphs. © 1929 John Wiley & Sons, Inc.     

On crossing of Gaussian fields

A formula is proved for the expectation of the (d?1)-dimensional measure of the intersection of a Gaussian stationary random field with a fixed level u.