**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.

**References**

[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.