Linear Crossing Numbers of Graphs (1973, 2009)

Originators: P. Erdős and R. Guy; D. Bienstock and N. Dean; Feder and Garber    (presented by Elyse Yeager - REGS 2012)

Definitions: A set of points in the plane is in general position if no three are in a line. A linear drawing of a graph $G$ is a drawing in which the vertices $V(G)$ of $G$ are represented as points in general position, and the edges $E(G)$ of $G$ are represented as line segments joining the appropriate pairs of points.

The crossing number of a graph $G$, written $\def\cr{{\rm cr}}\cr(G)$, is the minimum number of crossings of edges in a drawing of $G$ (not necessarily a linear drawing). In particular, $\cr(G)=0$ if and only if $G$ is planar.

The linear crossing number of $G$, written $\overline{\cr}(G)$, is the minimum number of crossings of edges in a linear drawing of $G$ (Erdős-Guy [EG]). Historically, the linear crossing number has been called the "rectilinear" crossing number, but there is nothing "recti" about it, since the edges need not be parallel to the axes. Note that always $\cr(G) \leq \overline{\cr}(G)$. Since the number of crossings in a linear drawing with $m$ edges is bounded above by ${m \choose 2}$, one can also consider the maximum number of crossings in a linear drawing of $G$; write this as $\overline{\cr}_\max(G)$.

Problem 1: Among connected graphs with $m$ edges and minimum degree $k$, what are the largest and smallest values of the linear crossing number and the maximum linear crossing number?

Definition: In a $t$-linear drawing, edges are represented by piecewise-linear curves consisting of at most $t$ line segments. The $t$-linear crossing number, written $\cr_t(G)$, is the minimum number of crossings of edges in such a drawing. Note that $\cr_1(G)=\overline{\cr}(G)$.

Question 2: (Bienstock) Is there a finite list of obstructions such that if $G$ contains no subdivision of a graph in this class (or no minor in this class), then the $t$-linear crossing number (for some small $t$) is bounded by some function of the crossing number?

Definition: Feder and Garber [FG] introduced another parameter involving crossings. Let $\mathcal{P}$ be a set of points in the plane, no three in a row, representing the vertices of $G$. A line $L$ separates points $p$ and $q$ if the line segment from $p$ to $q$ crosses $L$. For any two points $p,q \in \mathcal{P}$, let $n(p,q)$ be the number of lines defined by two points in $\mathcal P-\{p,q\}$ that separate $p$ from $q$. The orchard crossing number of a graph $G$, written OCN$(G)$, is $\min_{\mathcal P} \sum_{p,q \in E(G)}n(p,q)$.

Comments: Although OCN$(G)$ is a sum over edges in $G$, which are drawn as line segments, $n(p,q)$ counts lines (not segments) determined by pairs of points in $\mathcal P$. Also, crossings in the linear drawing of $G$ on $\mathcal P$ contribute to the count for each edge involved, so OCN$(G) \geq 2\overline{\cr}(G)$.

The orchard crossing number is known for disjoint union of cycles, windmills, $P_3$, $P_4$, the $n$-prism, complete bipartite graphs, complete graphs, stars, wheels, prisms, ladders, etc. The value is $0$ for cycles, disjoint unions of paths, and the claw.

Question 3: What other orchard crossing numbers can be computed? How does the OCN behave under the graph join or product operations? How large can OCN$(G)$ be when $G$ is an $n$-vertex planar graph? Can OCN be bounded above or below in terms of other graph parameters?

Definition: (Yeager, by misinterpreting the definition of OCN.) If we replace lines in the definition of OCN with line segments, we get the airport crossing number, or ACN$(G)$. Again, let $\mathcal P$ be a set of points in general position representing $V(G)$. We can speak of edges of $G$, which are drawn as line segments, and non-edges of $G$, which are line segments joining points in $\mathcal P$ corresponding to non-adjacent vertices of $G$. Crossing edges contribute 2 to the count. An edge crossing a non-edge contributes 1 to the count. Crossing non-edges contribute nothing. Note that ACN$(K_n)=$ OCN$(K_n)=2\overline{\cr}(K_n)$.

The motivation for the name "airport crossing number" is the problem of designing an airport. We want to lay out a collection of terminals, with hallways connecting some pairs. Certain pairs have high traffic joining them, and these will have moving walkways. When a hallway without a walkway intersects a hallway with a walkway, we must interrupt the walkway to allow the traffic to cross. When two hallways with walkways cross, we must break both walkways. These breaks are "expensive", so we want to minimize the total number of them.

Question 4: The same questions can be asked for ACN that are asked above about OCN? In addition, when are the two parameters equal? How large can their difference or ratio be?

Results: The airport count in any linear drawing of $G$ is at most the orchard count; hence ACN$(G)\le$OCN$(G)$. Still ACN$(G)\ge 2\overline\cr(G)$. In REGS, students Erickson, Kim, McConvey, Shar, Tomlinson, Wang, Yager, and Yeager have proved the following:
    $\circ$ ACN$(G) \geq \overline{\cr}(G)+\overline{\cr}(K_n)-\overline{\cr}_\max(\overline{G})$, although this often gives a trivial bound.
    $\circ$ ACN$(G) \leq \overline{\cr}_\max(G)+\overline{\cr}(K_n)$
    $\circ$ ACN$(G)=0$ for wheels, stars, double stars, $K_4$, theta graphs, disjoint cycles, caterpillars, squared paths with up to seven vertices, and their subgraphs. ACN$(K_{3,3})=2$.
    $\circ$ Any graph that properly contains $K_4$ has ACN at least 1.

[BD] Bienstock, D.; Dean, N.; New Results of Rectilinear Crossing Numbers and Plane Embeddings, J. Graph Theory, 16(1992), 389-398
[EG] Erdős, P.; Guy, R.K.; Crossing number problems, Amer. Math. Monthly 80 (1973), 52-58.
[FG] Feder, E.; Garber, D.; The orchard crossing number of an abstract graph, Proceedings of the Fortieth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congr. Numer. 197 (2009), 3-19.