返回Google圖書搜尋

Structural approach to the crossing number of graphs

其他書名	doctoral thesis
出版	D. Bokal, 2006
URL	http://books.google.com.hk/books?id=2-xYtwAACAAJ&hl=&source=gbs_api

註釋Crossing-critical graphs were introduced by Širáň, who proved existence of infinite families of $3$-connected $k$-crossing-critical graphs for every $k \ge 3$. Kochol proved existence of infinite families of simple $3$-connected $k$-crossing-critical graphs, $k \ge 2$. Richter and Thomassen started the research on degrees in crossing-critical graphs by proving that there are only finitely many simple $k$-crossing-critical graphs with minimum degree $r$ for every two integers $r \ge 6$ and $k \ge 1$. Salazar observed that their argument implies the same conclusion for every rational $r>6$, integer $k \ge 1$, and simple $k$-crossing-critical graphs with average degree $r$. For every rational $r \in [4,6)$ he proved existence of an infinite sequence $\{k_{r,i}\}_{i=0}^{\infty}$ such that for every $i \in \NN$ there exists an infinite family of simple $4$-connected $k_{r,i}$-crossing-critical graphs with average degree $r$ and asked about existence of such families for rational $r \in (3,4)$. The question was partially resolved by Pinontoan and Richter, who answered it positively for $r \in (3\frac{1}{2},4)$. In the present work we extend the theory of tiles, developed by Pinontoan and Richter, to encompass a generalization of the crossing-critical graphs constructed by Kochol. Combining tiles with a new graph operation, the zip product, which preserves the crossing number of the involved graphs, we settle the question of Salazar and combine the answer with the results of Širáň and Kochol into the following theorem: there exists a convex continuous function $f:(3,6) \to \RR^+$, such that, for every rational number $r \in (3,6)$ and every integer $k \ge f(r)$, there exists an infinite family of simple $3$-connected crossing-critical graphs with average degree $r$ and crossing number $k$. Beineke and Ringeisen investigated the crossing numbers of Cartesian products of small graphs with cycles and established the crossing numbers of the Cartesian product of $C_n \Box G$ where $G$ is any simple graph of order four, except the $3$-star, $K_{1,3}$. Jendrol' and Ščerbová closed this gap and also obtained the crossing number of $P_m \Box K_{1,3}$. They conjectured the general result for $P_m \Box K_{1,n}$, which was proven for $n=4$ by Klešč. We prove their conjecture in a slightly more general setting: by combining the result of Asano about the crossing number of $K_{1,3,n}$ with the zip product, we establish the crossing number of $T \Box K_{1,n}$ where $T$ is any tree of maximum degree three and $n \ge 3$ is any integer. We supplement this result by the crossing number of $T \Box K_{1,3}$ for any tree $T$, the crossing number of $P_m \Box W_n$ for any $m \ge 1$, $n \ge 3$, and some other exact results and bounds. Seymour regretted that the crossing number does not work well with graph minors, as the contraction of an edge can both increase and decrease the value of this graph invariant. We introduce the minor crossing number, a minor-monotone graph invariant that allows for further minimization of the number of crossings by allowing replacement of vertices by trees and minimizing the number of crossings in the resulting graph. We argue that this graph invariant is more natural in the VLSI applications than the ordinary crossing number, prove several general lower bounds on the minor crossing number, study the structure of graphs with bounded minor crossing number and provide some exact results and bounds for specific graphs. In particular, we generalize a result of Moreno and Salazar, who bounded the crossing number of a graph from below using the crossing number of its minor of small maximum degree.