The Orchard crossing number of an abstract graph
Elie Feder and David Garber
We introduce the Orchard crossing number, which is defined in a similar way to the well-known rectilinear crossing number. We compute the Orchard crossing number for some simple families of graphs. We also prove some properties of this crossing number. Moreover, we define a variant of this crossing number which is tightly connected to the rectilinear crossing number, and compute it for some simple families of graphs.
orch_crossing.tex
%3.5.07

\documentclass[10pt]{amsart}
\usepackage{amssymb,latexsym, amsthm,epsf}%, makeidx}
%\makeindex
\setlength\textwidth{4.5in}
\setlength\textheight{7.2in}

\newtheorem{thm}{Theorem}[section] %the resolution could also be [subsection]
\newtheorem{defn}[thm]{Definition}
\newtheorem{con}[thm]{Conjecture}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{const}[thm]{Construction}
\newtheorem{prob}[thm]{Problem}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{exa}[thm]{Example}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{rem}[thm]{Remark}
\newtheorem{algo}[thm]{Algorithm}
\newtheorem{notation}[thm]{Notation}%[section]

%%%%%%%%%%%% My definitions

\newcommand{\<}{\langle}
\renewcommand{\>}{\rangle}
\newcommand{\shortlen}[1]{\lfloor#1\rfloor}
%% Phrases
\def\bg{braid group}

%% Those Latin phrases
\def\ie{{i.e.}} % This form enables \ie,
\def\cf{{\it cf. \/}}
\def\viceversa{{\it vice versa}}
\def\Or{{\bf or}} % OK, not strictly Latin.
\def\And{{\bf and}} % OK, not strictly Latin.


%% Letters
\def\l{{\lambda}}
\def\lam{{\lambda}}
\def\s{\sigma}
%\def\s2{\sigma^2}
\def\ta{\tau}
\def\A{{\mathcal A}}
\def\C{{\mathbb C}}
\def\F{{\mathbb F}}
\def\Fx{{F[x]}}
\def\G{{\mathcal G}}
\def\I{{I}}
\def\II{{I\!\!I}} % I\!I is ok too, but I like this one better.
\def\N{{\mathbb N}}
\def\R{{\mathbb R}}
\def\P{{\mathbb P}}
\def\Q{{\mathcal{Q}}}
\def\CS{{\mathcal{S}}}
\def\Z{{\mathbb Z}}


%% Symbols
\newcommand\tensor[1][{}]{{\otimes_{#1}}}
\def\bigtensor{{\bigotimes}}
\def\la{{\leftarrow}}
\def\ra{{\rightarrow}}
\def\llra{{\longleftrightarrow}}
\def\minusset{{-}}
\def\o{\circ}
\def\sub{\subseteq}
\def\({\left(}
\def\){\right)}
\def\isom{{\cong}} % Meant to generate the = sign, with ~ above it

\newcommand\E{{\mathbb E}}
\newcommand\vol{\operatorname{vol}}

%% Operators
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\trKF}{tr_{K/F}}
\DeclareMathOperator{\Tr}{Tr}
\newcommand{\Norm}[1][{}]{{\operatorname{N}_{#1}}}
\newcommand\KK[1]{{\operatorname{K}_{#1}}} % Used for K_2 etc.
\DeclareMathOperator{\cores}{cor}
\newcommand\res[1][{}] {{\operatorname{res}_{#1}}}
\DeclareMathOperator{\Br}{Br}
\def\Brp{{{}_{p\!\!\!\:}\Br}} % Denotes the exponent $p$ part of $Br()$.
\DeclareMathOperator{\Cent}{Cent}
\DeclareMathOperator{\Ker}{Ker}
\DeclareMathOperator{\Gal}{Gal}
\DeclareMathOperator{\mychar}{char}
\newcommand{\sgn}[1]{{\operatorname{sgn}(#1)}}
\renewcommand{\Im}{{\operatorname{Im}}}
\newcommand\sep[1]{{{#1}_{\operatorname{s}}}} % Separable closure.
%\newcommand\len{{\operatorname{len}}}

%% Handling figures:
\newcommand\FIGURE[3][]{{\begin{figure} {\epsfbox{\figs{#2}}}\caption{#1}\label{#3}\end{figure}}}
\newcommand\FIGUREx[4][]{{\begin{figure}[!h]\epsfxsize=#3 %%@
{\epsfbox{\figs{#2}}}\caption{#1}\label{#4}\end{figure}}}
\newcommand\FIGUREy[4][]{{\begin{figure}[!h]\epsfysize=#3 %%@
{\epsfbox{\figs{#2}}}\caption{#1}\label{#4}\end{figure}}}


%% Misc. - mathematics
\newcommand{\set}[1]{{\{#1\}}}
\newcommand{\power}[1]{{\left|{#1}\right|}}
\newcommand{\mat}[4]{{\( \begin{array}{cc} {#1} & {#2} \\ {#3} & {#4} \end{array} \)}}
\newcommand{\amat}[2]{{\mat{#1}{#2}{#2}{#1}}}
\newcommand\ideal[1]{{\left<{#1}\right>}}
\newcommand\sg[1]{{\ideal{#1}}}
\newcommand\symb[3][] {{\{{{#2}},{{#3}}\}_{{#1}}}} % You can use \sybm{a}{b} or \symb[F]{a}{b}.
%\newcommand\symbalg[3][] {{({{#2}},{{#3}})_{{#1}}}} % You can use \sybmalg{a}{b} or %%@
%\symbalg[F]{a}{b}.
\newcommand\psymbalg[3][] {{[{{#2}},{{#3}})_{{#1}}}} % You can use \psybmalg{a}{b} or %%@
%\psymbalg[F]{a}{b}.
\newcommand\PP[1]{{{#1}^p-{#1}}}
\newcommand\dimcol[2]{{[{#1}\!:\!{#2}]}} % Produces nicely spaced [K:F]. Don't use in subscripts or %%@
%superscripts -- there LaTeX manages by his own.
\newcommand\suchthat{{\,:\,}}
\newcommand\subjectto{{\,|\,}}
\newcommand\divides{{\,|\,}}
\newcommand\mul[1]{{{#1}^{\times}}} % The multiplicative group

%% Misc. - LaTeX
\newcommand\eq[1]{{(\ref{#1})}}
\newcommand\Eq[1]{{Equation \eq{#1}}}
\newcommand\Eqs[2]{{Equations \eq{#1}--\eq{#2}}}
\newcommand\defin[1]{{\it{#1}}}
\long\def\forget#1\forgotten{}
\newcommand\notetxt[1]{{\textsf {#1}}}
\newcommand\notebox[2][4cm]{{\begin{tabular}{|p{#1}}\hline {#2} \\ \hline \end{tabular}}}
\newcommand\note[1]{{\marginpar{#1}}}
\newcommand\new[1]{{\note{{\it{#1:}}}}}
\newcommand{\sumlim}{\sum\limits}

\newif \iffurther %Give \section{Further ideas}
%\furthertrue
\furtherfalse

%%%%%%%%%%%%% End of definitions.


\newif \iffurther %Give \section{Further ideas}
%\furthertrue
\furtherfalse

%%%%%%%%%%%%% End of definitions.


%%%%%%%%%%%% XY package

\newif\ifXY % turns XY version on/off
%\XYtrue     % Turn it on
\XYfalse    % Turn it off

\ifXY
\usepackage{xy}
\fi
\ifXY
\xyoption{all}
\fi

%%%%%%%%%%%% End of XY

\begin{document}

\title{The Orchard crossing number of an abstract graph}

\author{Elie Feder and David Garber}

\address{Kingsborough Community College of CUNY, Department of Mathematics and Computer Science,
2001 Oriental Blvd., Brooklyn, NY 11235, USA}
\email{eliefeder@gmail.com, efeder@kbcc.cuny.edu}

\address{Department of Applied Mathematics, Holon Institute of Technology, Golomb 52,
PO Box 305, Holon 58102, Israel}
\email{garber@hit.ac.il}

\date{\today}

\begin{abstract}
We introduce the Orchard crossing number, which is defined in
a similar way to the well-known rectilinear crossing number. We
compute the Orchard crossing number for some simple families of
graphs. We also prove some properties of this crossing number.

Moreover, we define a variant of this crossing number which is
tightly connected to the rectilinear crossing number, and compute it
for some simple families of graphs.
\end{abstract}

\maketitle

\section{Introduction}
Let $G$ be an abstract graph. Motivated by the Orchard relation,
introduced in \cite{bacher,BaGa}, one can define the {\it Orchard
crossing number} of $G$, in a similar way to the well-known {\it
rectilinear crossing number} of an abstract graph $G$ (denoted by
$\overline{\rm cr}(G)$, see \cite{aak2,PT}).

The Orchard crossing number is interesting for several reasons.
First, it is based on the Orchard relation which is an equivalence
relation on the vertices of a graph, with at most two equivalence
classes (see \cite{bacher}). Moreover, since the Orchard relation
can be defined for higher dimensions too (see \cite{bacher}),
hence the Orchard crossing number
may be also generalized to higher dimensions.

Second, a variant of this crossing
number is tightly connected to the well-known rectilinear crossing number (see
Proposition \ref{max_complete}).

Third, one can find real problems which the Orchard crossing number
can represent.  For example, design a network of computers which should be
constructed in a manner which allows possible extensions
of the network in the future. Since we want to avoid (even future) crossings
of the cables which are connecting between the computers, we need to count not
only the present crossings, but also the separators
(which might come to cross in the future).


In the current paper, we define the Orchard crossing number for an
abstract graph $G$, and we compute it for some simple families of graphs.
We also deal with some simple properties of this crossing
number. Some more properties can be found at \cite{GPS}.

We also define some variant of this crossing number, which is
tightly connected to the rectilinear crossing number, and we compute
it for some simple families of graphs.

\medskip

The paper is organized as follows. In Section \ref{defs}, we present
the Orchard relation, define the Orchard crossing number and its
variant, and give some examples.
In Section \ref{crossing_complete}, we compute the Orchard crossing number for
the complete graph $K_n$.
Section \ref{star} deals with the Orchard crossing number of the star graph $K_{n,1}$.
In Section \ref{wheel}, we compute the Orchard crossing number for
the wheel graph $W_{n,1}$.
Section \ref{bipartite} deals with some partial results about complete
bipartite graphs $K_{n,m}$.
In Section \ref{union}, we discuss the computation of the Orchard crossing number 
for a particular case of a union of two graphs.


\section{The Orchard relation and the Orchard crossing
numbers}\label{defs}

We start with some notations.
A finite set $\mathcal P = \{P_1,\cdots, P_n\}$ of $n$ points
in the plane $\R^2$ is a {\it generic configuration}
if no three points of $\mathcal P$ are collinear.

A line $L \subset \R^2$ {\it separates} two points $P,Q \in
(\R^2\setminus L)$ if $P$ and $Q$ are in different connected
components of $\R^2 \setminus L$. Given a generic configuration
$\mathcal P$, denote by $n(P,Q)$ the number of lines defined by
pairs of points in $\mathcal P \setminus \{P,Q\}$, which separate
$P$ and $Q$.

In this situation, one can define:
\begin{defn}[Orchard relation]
For two distinct points $P,Q$ of a generic configuration ${\mathcal P}$,
we set $P \sim Q$ if we have
$$n(P,Q) \equiv (n-3) \pmod 2.$$
\end{defn}

One of the main results of \cite{bacher} is that this relation is an
equivalence relation, having at most two equivalence classes.
Moreover, this relation can be used as an (incomplete) distinguishing
invariant between generic configurations of points.

\medskip

In order to define the {\it Orchard crossing number}, we need some more notions.

\begin{defn}[Rectilinear drawing of an abstract graph $G$]
Let $G=(V,E)$ be an abstract graph.
{\em A rectilinear drawing of a graph $G$}, denoted by $R(G)$, is a generic subset of points $V'$
in the affine plane, in bijection with $V$. An edge $(s,t)\in E$ is
represented by the straight segment $[s',t']$ in $\R^2$.
\end{defn}

One then can associate a {\it crossing number} to such a drawing:
\begin{defn}
Let $R(G)$ be a rectilinear drawing of the abstract graph $G=(V,E)$.
The {\em crossing number} of $R(G)$, denoted by $n(R(G))$, is:
$$n(R(G)) = \sum _{(s,t) \in E} n(s,t)$$
\end{defn}

Note that the sum is taken only over the edges of the graph, whence $n(s,t)$
counted in {\it all} the lines generated by pairs of points of the configuration.

\medskip

Now, we can define the {\it Orchard crossing number} of an abstract
graph $G=(V,E)$:

\begin{defn}[Orchard crossing number]
Let $G=(V,E)$ be an abstract graph.
The {\em Orchard crossing number} of $G$, ${\rm OCN}(G)$, is
$${\rm OCN}(G) = \min _{R(G)} (n(R(G)))$$
\end{defn}

\medskip

Note that the usual intersection of two edges contributes two separations:
Each edge separates the two
points at the ends of the other edge. Hence, one have the following
important observation:
\begin{rem}
Let $G$ be an abstract graph. Then:
$$\overline{\rm cr}(G) \leq \frac{1}{2} {\rm OCN}(G)$$
where the rectilinear crossing number of an abstract graph $\overline{\rm cr}(G)$
is defined to be the smallest number of crossings between edges in a
rectilinear drawing of the graph $G$.
\end{rem}

Hence, by computing the Orchard crossing number of a graph, one gets
also some upper bounds for the rectilinear crossing number (these
bounds are rather bad, see the table after Proposition
\ref{complete}. The reason for the bad bounds is that the best drawing
with respect to the Orchard crossing number is rather worse with
respect to the rectilinear crossing number, see Proposition
\ref{complete}).

\medskip

A variant of the Orchard crossing number is the {\it maximal Orchard crossing number}:

\begin{defn}[Maximal Orchard crossing number]
Let $G=(V,E)$ be an abstract graph. The {\em maximal Orchard crossing
number} of $G$, ${\rm MOCN}(G)$, is
$${\rm MOCN}(G) = \max _{R(G)} (n(R(G)))$$
\end{defn}

This variant is extremely interesting due to the following result:

\begin{prop}\label{max_complete}
The drawing which yields the maximal Orchard crossing number for
complete graphs $K_n$ is the same as the drawing which attains the
rectilinear crossing number of $K_n$.
\end{prop}

The importance of this result is that it might be possible that the
computation of the maximal Orchard crossing number is easier than
the computation of the rectilinear crossing number.

\begin{proof}
Let us look on quadruples of points: there are only two
possibilities to draw four points in a generic position, see Figure \ref{quadraple}.

\begin{figure}[h]
\epsfysize=3cm \centerline{\epsfbox{quadraple.eps}} \caption{Two
generic configurations of $4$ points} \label{quadraple}
\end{figure}

Note that $\overline{\rm cr}(K_4)=0$, since we can draw $K_4$ without
any crossings of the edges (type (b)). Hence, for getting the
minimal rectilinear drawing for $K_n$ with respect to the
rectilinear crossing number, we would like to have as many as
possible quadruples of points arranged as in type (b).

On the other hand, for getting the maximal number of crossings with
respect to the Orchard crossing number, we would like again to have
as many as possible quadruples of points arranged as in type (b),
since type (a) contributes 2 crossings (each internal edge
separates the two ends of the other internal edge) while type (b)
contributes 3 crossings (one on each edge of the convex hull).
Hence, the rectilinear drawing which yields the maximal number of
crossings with respect to the Orchard crossing number, will also give
the minimal number of crossings with respect to the rectilinear
crossing number.
\end{proof}



\subsection{Some examples}

In this subsection, we give some examples for computing the Orchard
crossing numbers for some small graphs.

\medskip

The Orchard crossing number of $K_4$ is $2$, since there are only
two generic drawings of four points as presented in Figure
\ref{quadraple}. Type (a) has $2$ crossings, while type (b) has $3$
crossings. Therefore:
$${\rm OCN}(K_4)=2.$$
$${\rm MOCN}(K_4)=3.$$

\medskip

For the complete bipartite graph $K_{2,2}$, we have more
possibilities for rectilinear drawings, since except for the two
choices for drawings, we have also to choose the two pairs of
points. Figure \ref{4bipartite}(a) shows a drawing of $K_{2,2}$ without
crossings at all (we distinguish between the two sets of two points
by their colors). On the other hand,  Figure \ref{4bipartite}(b) shows a
rectilinear drawing of $K_{2,2}$ with $2$ crossings. Hence, we get that
$${\rm OCN}(K_{2,2})=0.$$
$${\rm MOCN}(K_{2,2})=2.$$

\begin{figure}[h]
\epsfysize=2.5cm \centerline{\epsfbox{4bipartite.eps}} \caption{Generic rectilinear drawings of $K_{2,2}$}\label{4bipartite}
\end{figure}

Note that $K_{2,2} \cong C_4$ where $C_4$ is the cycle graph on $4$
vertices, and it is shown in \cite{GPS} that the graphs whose
Orchard crossing number equals $0$ are the following:
\begin{enumerate}
\item The cycle graphs, $C_n$, and their subgraphs.
\item The graph on $4$ vertices presented in Figure \ref{graph_4}.

\begin{figure}[h]
\epsfysize=2cm \centerline{\epsfbox{graph_4.eps}} \caption{An example of a graph
with ${\rm OCN}(G)=0$} \label{graph_4}
\end{figure}

\end{enumerate}




\section{Orchard crossing numbers for complete graphs $K_n$}\label{crossing_complete}

For the complete graphs $K_n$, we have the following proposition:

\begin{prop}\label{complete}
Let $n \in \N$. Then
$${\rm OCN}(K_n)=2{n \choose 4},$$
which is obtained by placing all vertices of $K_n$ in a convex
position.
\end{prop}

\begin{proof}
Since there are only two generic rectilinear drawings of four points
(as presented in Figure \ref{quadraple}), any quadruple of points
can contribute $2$ (type (a)) or $3$ (type (b)) to the total number
of crossings.

Since we want to minimize the total number of crossings, we have to
require that every quadruple of  points will be in a convex
position. This immediately implies that all $n$ points have to be in
 a convex position  as needed.

The computation of the crossing number is straight-forward: from the
configuration of $n$ points, we can choose ${n \choose 4}$ different
quadruples of points, and each quadruple contributes $2$ to the
total number of crossings, which implies that the total number of
crossings is $2{n \choose 4}$.
\end{proof}

Based on the last proposition, we compare in the following table between
the Orchard crossing numbers and the rectilinear crossing numbers
for the complete graph $K_n$, for $n \leq 12$.

\medskip

$$\begin{array}{|c|c|c|}
\hline
n   & {\rm OCN}(K_n)         & \overline{\rm cr}(K_n)      \\
\hline
 4  & 2                      &  0                     \\
 5  & 10                     &  1                     \\
 6  & 30                     &  3                     \\
 7  & 70                     &  9                     \\
 8  & 140                    &  19                    \\
 9  & 252                    &  36                    \\
 10 & 420                    &  62                    \\
 11 & 660                    &  102                   \\
 12 & 990                    &  153                   \\
\hline
\end{array}$$

\medskip

Note that up to $n = 27$, $\overline{\rm cr}(K_n)$ is known, and for $n \geq 28$,
only bounds are known (see \cite{AFLS,aak2,AGOR,ak2,aor}).


\section{Orchard crossing numbers for the star graph $K_{n,1}$}\label{star}

In this section, we deal with the Orchard crossing number of the graph $K_{n,1}$ (which is also called the {\it star graph}).
Assume that we have $n$ black points and one white point, and the white point is connected to all the black points.
Then, the following holds:

\begin{prop}\label{k_m1_prop}
The configuration of $n+1$ points which attains the minimal number of
Orchard crossings  for the graph $K_{n,1}$ consists of $n$ black points which are the
vertices of a regular $n$-gon, and the white point is located at the
center of this polygon for odd $n$, or close to its center (i.e. it
is not separated by a line from the center), for even $n$ (see
Figure \ref{k_m1} for examples of $n=7,8$).

\begin{figure}[h]
\epsfysize=5cm \centerline{\epsfbox{k_m1.eps}} \caption{Examples of
$K_{n,1}$ for odd $n$ and for even $n$} \label{k_m1}
\end{figure}


Hence, we have:
$$
{\rm OCN}(K_{n,1})=\left\{
\begin{array}{cl}
            \frac{n(n-1)(n-3)}{8}  &  {\rm odd}\ n \\
            \frac{n(n-2)^2}{8}     &  {\rm even}\ n
\end{array}
\right.
$$

\end{prop}

\begin{proof}
As in the proof of Proposition \ref{complete},
we start by looking on quadruples of points. We have three cases of
three black points and one white point (we exclude the case of quadruples of
four black points, since it contributes nothing in any position):
\begin{enumerate}
\item A white point inside a triangle of black points
(see Figure \ref{bipartite3-1}(a)). This quadruple contributes
nothing to the total number of crossings.
\item Three black points and one white point in a convex position
(see Figure \ref{bipartite3-1}(b)). This quadruple contributes $1$
to the total number of crossings.
\item A black point inside a triangle consists of one white point and
two black points (see Figure \ref{bipartite3-1}(c)). This quadruple
contributes $2$ to the total number of crossings.
\end{enumerate}

\begin{figure}[h]
\epsfysize=3cm \centerline{\epsfbox{bipartite3-1.eps}}
\caption{Three types of quadruples of points with three black points
and one white point} \label{bipartite3-1}
\end{figure}

Our aim is to minimize the number of quadruples of types (2) and (3)
as a whole. Later, we will minimize the number of quadruples of type
(3) as opposed to those of type (2). In order to compute the number
of quadruples of types (2) and (3) in a given drawing of $K_{n,1}$,
we label the black points $b_1, b_2,\dots,b_n$ and the white point
$w$.

For each $1 \leq i \leq n$, let $L_i$ be the line which connects
$b_i$ to $w$. This line divides the remaining $n-1$ black points
into two subsets - one contains $k_i$ points, and the other
contains $(n-1)-k_i$ points. For each pair of points, $b_j$ and
$b_k$, situated on the same side of $L_i$, the quadruple $b_i, b_j,
b_k, w$, is of type (2) or (3) and hence contributes at least one
crossing. We have ${k_i \choose 2} + {(n-1)-k_i \choose 2}$ such
pairs of points. Thus in total we have $\sumlim_{i=1}^n \left( {k_i
\choose 2} + {(n-1)-k_i \choose 2} \right)$ quadruples of types (2)
or (3). (Note that if $b_j$ and $b_k$ are separated by $L_i$, then
the quadruple $b_i, b_j, b_k, w$, is of type (1) or (2) and hence
contributes at most one crossing.)

Note that each quadruple is counted twice due to the following
reason. Consider the quadruple $b_i, b_j, b_k, w$. Assume, without
loss of generality, that $b_i, b_j$ and $b_k$ are oriented in
clockwise fashion around $w$. Then, both lines $L_i$ and $L_k$ give
this quadruple. However, the line $L_j$ separates $b_i$ from $b_k$
and therefore will not give this quadruple. So we divide the above
number of quadruples by $2$.

Since each quadruple of type (2) or type (3) contributes at least one
crossing, we have at least $$\frac{\sumlim_{i=1}^n \left( {k_i
\choose 2} + {(n-1)-k_i \choose 2} \right) }{2}$$ crossings.

This sum is minimized if $k_i = \frac{n-1}{2}$ for all $i$, i.e.
every line connecting the white point to a black point divides the
remaining black points into two subsets with the same number of
points (or different by 1 for even $n$). This condition will be
satisfied only if the $n$ points are evenly distributed around the
white point.

In order to determine the distance of the $n$ black points to the white
point, we consider types (2) and (3). In order to avoid any
quadruple of type (3), we have to ensure that each quadruple $b_i,
b_j, b_k, w$ is in a convex position. This will be accomplished only
if the $n$ black points are all in a convex position around the white point.
In this case, every quadruple which contains a white point, will be
of type (2) and therefore will contribute only one crossing. This
gives us the requested minimal rectilinear drawing.

\medskip

Therefore, we can compute the number of crossings as follows. For
odd $n$, we have $k_i=\frac{n-1}{2}$ for all $1 \leq i \leq n$.
Thus, we have:
\begin{eqnarray*}
{\rm OCN}(K_{n,1}) &= & \frac{\sumlim_{i=1}^n \left( {\frac{n-1}{2}
\choose 2} +
{(n-1) - \frac{n-1}{2} \choose 2} \right) }{2} = \\
&= & n {\frac{n-1}{2} \choose 2} = \frac{n\left(\frac{n-1}{2}\right)\left(\frac{n-3}{2}\right)}{2} =\\
& =& \frac{n(n-1)(n-3)}{8}.
\end{eqnarray*}

For even $n$, we have $k_i=\frac{n}{2}$ for all $1 \leq i \leq n$.
Thus, we have:
\begin{eqnarray*}
{\rm OCN}(K_{n,1}) & =& \frac{\sumlim_{i=1}^n \left( {\frac{n}{2}
\choose 2} +
{(n-1) - \frac{n}{2} \choose 2}\right)}{2} =\\
&= & \frac{\sumlim_{i=1}^n \left( {\frac{n}{2} \choose 2} + { \frac{n-2}{2} \choose 2} \right)}{2} = \\
&=& n \cdot \frac{\frac{\left(\frac{n}{2}\right)
\left(\frac{n-2}{2}\right)}{2} +
\frac{\left(\frac{n-2}{2}\right) \left(\frac{n-4}{2}\right) }{2}}{2}=\\
&=& \frac{n(n-2)(n+n-4)}{16}=\\
&=& \frac{n(n-2)(2n-4)}{16} = \frac{n(n-2)^2}{8}.
\end{eqnarray*}

\end{proof}

In the following lemma, we present a different way to count the number of Orchard
crossings in the minimal rectilinear drawing, as in Proposition
\ref{k_m1_prop}.

\begin{lem}
$$
{\rm OCN}(K_{n,1})=\left\{
\begin{array}{cl}
            \frac{n(n-1)(n-3)}{8}  &  {\rm odd}\ n \\
            \frac{n(n-2)^2}{8}     &  {\rm even}\ n
\end{array}
\right.
$$
\end{lem}

\begin{proof}
Since there are no quadruples of type (3) (since the only internal
point is white), all the crossings come from quadruples of type (2),
which contribute one crossing for each quadruple. So, we have to
count the number of quadruples of type (2): quadruples with three
black points and one white point in a convex position.

In the odd case, since the white point is in the center of the
$n$-gon, for having a quadruple of type (2), all the black points should
be within $180^{\circ}$ of each other. For counting the number of
such triples, we fix one black point. The other two points should be
within $180^{\circ}$ from this point. This gives us $\frac{n-1}{2}$
options to choose two points from. We can do this in ${\frac{n-1}{2}
\choose 2}$ ways. Now since we could have started with any of the
$n$ points, we have to multiply it by $n$. So, we get:
$$n {\frac{n-1}{2} \choose 2} = \frac{n \cdot \frac{n-1}{2}
\frac{n-3}{2}}{2} = \frac{n(n-1)(n-3)}{8},$$ as needed.

\medskip

Now we turn to the even case. This case is more complicated, since
if we choose two antipodal black points, we have to cut the number
of quadruples by $2$, due to the central white point which is not
located exactly at the center (see Figure \ref{k_m1}, $n=8$). So, we
split the count of triples into two cases: triples which do not
include antipodal points, and triples which include antipodal
points.

We start with the case which does not include antipodal points: Fix a
black point. We have to choose two black points out of $\frac{n-2}{2}$
options. Hence,  we have ${\frac{n-2}{2} \choose 2}$ possibilities , and we have in total:
$$n {\frac{n-2}{2} \choose 2} = \frac{n(n-2)(n-4)}{8}$$   crossings.

Now we count the number of triples which include antipodal points:
We have $\frac{n}{2}$ pairs of points in antipodal position.
The third point can be any of the other $n-2$ points. Since
we only count half of these triples (as explained above), we have
$\frac{n(n-2)}{4}$ crossings.

Summing up the two cases, we get:
$$ \frac{n(n-2)(n-4)}{8} + \frac{n(n-2)}{4} = \frac{n(n-2)(n-2)}{8},$$
again as needed.
\end{proof}


\section{Orchard crossing number of a wheel}\label{wheel}

In this section, we deal with the Orchard crossing number of a {\it
wheel}, which is an abstract graph on $n+1$ points, which is
composed of a cycle of $n$ points and one other point connected
to each point of the cycle (see Figure \ref{wheel_fig} for an example). We denote
such a graph by $W_{n,1}$

\begin{figure}[h]
\epsfysize=3cm
\centerline{\epsfbox{wheel.eps}}
\caption{The wheel graph $W_{5,1}$} \label{wheel_fig}
\end{figure}

Before stating the general case, a simple observation yields the following facts:
\begin{rem}
$${\rm OCN}(W_{3,1})=2$$
$${\rm OCN}(W_{4,1})=6$$
\end{rem}

\begin{proof}
Note that $W_{3,1}=K_4$, and hence the result follows.

For $W_{4,1}$, we have two optimal drawings, each of them has $6$ crossings, see Figure \ref{OCN_draws_W4-1}.

\begin{figure}[h]
\epsfysize=3cm
\centerline{\epsfbox{OCN_draws_W4-1.eps}}
\caption{Two optimal drawings for $W_{4,1}$} \label{OCN_draws_W4-1}
\end{figure}


\end{proof}

Here we present the general case:
\begin{prop}\label{wheel_prop}
Let $n \geq 5$. Let $G=W_{n,1}$ be a graph consisting of $n+1$
vertices configured as a wheel.

The configuration of $n+1$ points which attains the minimal number of
Orchard crossings consists of $n$ points which are the vertices of a
regular $n$-gon (these points form the cycle), and the other point
is located at the center of this polygon for odd $n$, or close to
its center (i.e. it is not separated by a line from the center) for
even $n$.

Hence, we have:
$$
{\rm OCN}(W_{n,1})=\left\{
\begin{array}{cl}
            \frac{n(n^2 - 4n + 11)}{8}  &  {\rm odd}\ n \\
            \frac{n(n^2 - 4n + 12)}{8}  &  {\rm even}\ n
\end{array}
\right.
$$

\end{prop}

First we will prove that this drawing minimizes the crossings for a
wheel. Notice that a wheel $W_{n,1}$ is very similar to $K_{n,1}$.
The only difference is that in $W_{n,1}$, we have an additional cycle on the $n$
external points.

For $K_{n,1}$, we know that the above configuration minimizes the
number of crossings. Thus, all we have to show is that the addition
of the cycle maintains the minimality. Hence, we have to consider
how many crossings are added by the addition of the cycle in the
optimal configuration, and how many are added in other
configurations.

There are two types of edges in our configuration:
\begin{enumerate}
\item the edges on the cycle, and

\item the edges which connect the center and an external point.
\end{enumerate}


Let us consider them one at a time.

\begin{enumerate}
\item The edges of the cycle do not separate between any pair of points in the
configuration.

\item Each edge connecting the center and an external point will
intersect the cycle once (where the continuation of the edge crosses
the convex hull). This intersection contributes $1$ to the total
number of crossings (because this edge separates the vertices on the
cycle).
\end{enumerate}

Since we have $n$ external points, we conclude that the addition
of the cycle contributes $n$ crossings in total. Now let us consider
how many crossings the addition of the cycle contributes in other
configurations.

\begin{lem}
Let $R(W_{n,1})$ be a rectilinear drawing for the wheel
$W_{n,1}$. Then, we have for $n \geq 5$:
$$n(R(W_{n,1})) \geq {\rm OCN}(K_{n,1}) + n,$$
\end{lem}

\begin{proof}
We split the proof into two cases, depending on the position
of the central point of the wheel in the drawing.

\medskip

\noindent {\bf Case 1:} If the central point of the wheel is inside
the convex hull generated by the points of the cycle,
then for any edge connecting the center and an
external point, the extension of this edge separates two points on
the convex hull of the cycle. This occurs where the extension of the edge exits the
interior of the cycle. Since we have $n$ points on the cycle, we add at
least $n$ crossings. Hence, we have:
$$n(R(W_{n,1})) \geq n(R(K_{n,1}))+n \geq {\rm OCN}(K_{n,1}) + n,$$
(where $R(K_{n,1})$ is the corresponding drawing for $K_{n,1}$).

\medskip

\noindent {\bf Case 2:} If the central point of the wheel is outside
the convex hull generated by the points of the cycle, we just show that
$$n(R(W_{n,1})) \geq {\rm OCN}(K_{n,1}) + n.$$
by a direct computation: in case that the central point of the wheel is outside
the convex hull generated by the points of the cycle, each quadruple involved the central point and
three points of the cycles contributes at least one crossing (see types (b) and (c) in Figure \ref{bipartite3-1}). Since we have $n \choose 3$ such quadruples,
we have $n(R(W_{n,1})) \geq {n \choose 3}$. On the other hand, for $n \geq 5$,
$${n \choose 3} \geq {\rm OCN}(K_{n,1}) + n$$
since for odd $n$ (the even case is similar), we have:
\begin{eqnarray*}
& &{n \choose 3} - ({\rm OCN}(K_{n,1})\ + n)=\\
&=&\frac{n(n-1)(n-2)}{6}-\frac{n(n-1)(n-3)}{8}-n=\\
&=&\frac{4n(n-1)(n-2)-3n(n-1)(n-3)-24n}{24}=\\
&=&\frac{n^3-25n}{24}\geq 0
\end{eqnarray*}
\end{proof}

Hence, we conclude that the rectilinear drawing of the wheel with the minimal
number of Orchard crossings is as stated in Proposition
\ref{wheel_prop}.

To verify that the values of ${\rm OCN}(W_{n,1})$
which stated in Proposition \ref{wheel_prop} are correct, we simply
have to take the values for ${\rm OCN}(K_{n,1})$ and add $n$ for the
$n$ crossings contributed by the edges of the cycle (as above).



\section{Complete bipartite graphs of type $K_{n,m}$}\label{bipartite}

The case of complete bipartite graphs of type $K_{n,n}$ is complicated,
and we leave its long proof of the following proposition to a different paper \cite{FG}:
\begin{prop}
$${\rm OCN}(K_{n,n})=4n{n \choose 3},$$
which is achieved by the regular $2n$-gon, alternating in colors.
\end{prop}

\medskip

In Table \ref{table1}, we summarize our computational results (based on the database of Aichholzer, Aurenhammer and Krasser \cite{aak})
for the Orchard crossing number for some complete bipartite graphs
$K_{n,m}$, where $n \not = m$, $n >1$ and  $m >1$. In this table,
the rows will be the different values of $n$, and the columns will
be the different values of $m$.

\begin{table}[!h]
\centerline{\begin{tabular}{|l|r|r|r|r|r|}
\hline
n:  /  m:           & 2  &  3  & 4  & 5  & 6  \\
\hline
   2                & 0  &  4  & 12 & 26 & 48 \\
   3                & 4  &  12 & 32 & 63 &    \\
   4                & 12 &  32 & 64 &    &    \\
   5                & 26 &  63 &    &    &    \\
   6                & 48 &     &    &    &    \\
\hline
\end{tabular}}
\caption{${\rm OCN}(K_{n,m})$ for different values of $n$ and $m$}\label{table1}
\end{table}


\subsection{The maximal Orchard crossing number for complete bipartite graphs
$K_{n,m}$}\label{max_crossing_bipartite}

In this section, we deal with the maximal Orchard crossing number of bipartite graphs $K_{n,m}$.
Assume that we have $n$ black points and $m$ white points, and all the white points are connected to all the black points.
Then, the following holds:

\begin{prop}\label{mocn_bipartite}
The configuration of $n+m$ points which attains the maximal number of
Orchard crossings  for the graph $K_{n,m}$ consists of $n$ black points and $m$ white points which are organized
on two arcs facing each other, where the black points are located on one arc
and the white points are located on the other arc (see
Figure \ref{mocn_K44} for an example for $n=m=4$).

\begin{figure}[h]
\epsfysize=3cm
\centerline{\epsfbox{mocn_K44.eps}}
\caption{The optimal drawing for ${\rm MOCN}(K_{4,4})$} \label{mocn_K44}
\end{figure}

Hence, we have:
$$
{\rm MOCN}(K_{n,m})=2{n \choose 2}{m \choose 2} + 2m{n \choose 3}+2n{m \choose 3}
$$

\end{prop}

\begin{proof}
As in the previous proofs, we start by looking on quadruples of points. We have three types of quadruples with
two black points and two white points:
\begin{enumerate}
\item Two black points and two white points in a convex position and the points alternate in colors
(see Figure \ref{max_bipartite2-2}(a)). This quadruple contributes
nothing to the total number of crossings.

\item Two black points and two white points in a convex position and the points do not alternate in colors
(see Figure \ref{max_bipartite2-2}(b)). This quadruple contributes
$2$ to the total number of crossings.

\item Two black points and two white points which are not in a convex position
(see Figure \ref{max_bipartite2-2}(c)). This quadruple contributes
$2$ to the total number of crossings.
\end{enumerate}

\begin{figure}[h]
\epsfysize=2.5cm
\centerline{\epsfbox{max_bipartite2-2.eps}}
\caption{Three cases of quadruples of points with two black points
and two white points} \label{max_bipartite2-2}
\end{figure}

On the other hand, as in the proof of Proposition \ref{k_m1_prop}, we have three types of quadruples with three black points and one white point:
\begin{enumerate}
\item The three black points are in the convex hull and the white point is inside this triangle (see Figure \ref{bipartite3-1}(a)).
This quadruple contributes nothing to the total number of crossings.

\item All the four points are in a convex position
(see Figure \ref{bipartite3-1}(b)). This quadruple contributes
$1$ to the total number of crossings.

\item The convex hull consists of two black points and a white point
(see Figure \ref{bipartite3-1}(c)). This quadruple contributes
$2$ to the total number of crossings.
\end{enumerate}

We shall show that the drawing appearing in the formulation of the proposition indeed attains the maximal possible number
of Orchard crossings for the graph $K_{n,m}$. Let us start with quadruples with two black points and two white points. The maximal number of
crossings which such a quadruple can contribute is $2$. In the above drawing, all the quadruples consisting on two black points
and two white points indeed contribute $2$ (all the quadruples are organized as in type (b)).

Now we move to quadruples with three points of one color and one point of the other color. For such quadruples, the maximal number of
crossings is again $2$. Note that in the above drawing, all the quadruples of this type indeed contribute $2$ (all the quadruples are
organized as in type (c)).

Hence, we get that the drawing appearing in the formulation of the proposition indeed attains the maximal possible number
of Orchard crossings for $K_{n,m}$.

\medskip

For computing ${\rm MOCN}(K_{n,m})$, we simply count the number of quadruples of the different types:
\begin{enumerate}
\item We have ${n \choose 2}{m \choose 2}$ quadruples with two black points and two white points,
since for constructing such a quadruple, we have to choose two black points
(out of $n$) and two white points (out of $m$). Since each quadruple contributes $2$,
the total contribution of these quadruples is $2{n \choose 2}{m \choose 2}$.

\item We have $n{m \choose 3}$ quadruples with one black point and three white points,
since for constructing such a quadruple, we have to choose one black point
(out of $n$) and three white points (out of $m$). Similarly, we have $m{n \choose 3}$
quadruples with one white point and three black points. Since each quadruple contributes $2$,
the total contribution of these quadruples is $2m{n \choose 3}+2n{m \choose 3}$.
\end{enumerate}

Summing up the contributions, we get the desired result.
\end{proof}



\section{The Orchard crossing number of a union of two
graphs}\label{union}

In this section, we deal with the question: what happens to the
Orchard crossing number when we unite two graphs.

We deal with a property of a union of two special graphs:
\begin{prop}
 Let $G$ and $H$ be two graphs on the {\em same} set of vertices.
Assume that $G$ and $H$ get the minimal number of Orchard crossings
in the same rectilinear drawing $C$. Assume also that $H$ is
contained in the complement of $G$ (so they have no edge in common).

Then, the configuration $C$ is the minimal configuration with
respect to the Orchard crossing number for $G \cup H$, and:
$${\rm OCN}(G \cup H)={\rm OCN}(G) + {\rm OCN}(H).$$
\end{prop}

\begin{proof}
Assume on the contrary that there is a better rectilinear drawing
for $G \cup H$. Since in the better rectilinear drawing, ${\rm
OCN}(G \cup H) < {\rm OCN}(G) +{\rm OCN}(H)$, at least one of the
following will occur:

\begin{enumerate}
\item If we delete the edges of $H$, we get a better rectilinear drawing for
$G$, or
\item  If we delete the edges of $G$, we get a better rectilinear
drawing for $H$,
\end{enumerate}
which is a contradiction.
\end{proof}


\begin{rem}
Although one can decompose $W_{n,1}$ into a disjoint union of $K_{n,1}$
and a cycle of length $n$, $C_n$, we can not apply the last proposition, since
the cycle of length $n$ has another isolated vertex, and hence its minimal drawing
is no more $n$ points in convex position and one point inside (as in Figure \ref{Cn_U_pt}(a),
which has $n$ crossings), but $n+1$ points in a convex position (as in Figure \ref{Cn_U_pt}(b), which
has $n-2$ crossings).

\begin{figure}[h]
\epsfysize=3cm
\centerline{\epsfbox{Cn_U_pt.eps}}
\caption{Two drawings of a cycle of length $n=5$ with additional isolated vertex} \label{Cn_U_pt}
\end{figure}


\end{rem}





\section*{Acknowledgments}

We wish to thank Roland Bacher for fruitful discussions. The second
author wish to thank Mikhail Zaidenberg and Institut Fourier for
hosting his stay in Grenoble, where this research was initiated.

\begin{thebibliography}{99}
\bibitem{AFLS} Abrego, B.M., Fernandez-Merchant, S., Leanos, J. and Salazar, G., {\it The maximum number of halving lines and the rectilinear crossing number of $K_n$ for $n \leq 27$}, Electronic Notes in Discrete Math. {\bf 30} (2008), 261--266.
\bibitem{aak} Aichholzer, O., Aurenhammer, F. and Krasser, H.,
    {\it Enumerating order types for small point sets with
    applications}, in: Proc. 17th Ann. ACM Symp. Computational
    Geometry, 11--18, Medford, Massachusetts, USA, 2001.
\bibitem{aak2} Aichholzer, O., Aurenhammer, F. and Krasser, H.,
    {\it On the crossing number of complete graphs}, in: Proc. 18th
    Ann. ACM Symp. Computational Geometry, 19--24, Barcelona, Spain, 2002.
\bibitem{AGOR} Aichholzer, O., Garcia, J., Orden, D. and Ramos, P., {\it New lower bounds
    for the number of ($\leq k$)-edges and the rectilinear crossing number of $K_n$},
    Discrete Comput. Geom. {\bf 38}(1) (2007), 1--14.
\bibitem{ak} Aichholzer, O. and Krasser, H., {\it The point set order
    type data base: A collection of applications and results}, in: Proc. 13th
    Annual Canadian Conference on Computational Geometry CCCG 2001,
    17--20, Waterloo, Ontario, Canada, 2001.
\bibitem{ak2} Aichholzer, O. and Krasser, H., {\it Abstract order type extension and
    new results on the rectilinear crossing number}, Computational
    Geometry: Theory and Applications, Special Issue on the 21st
    European Workshop on Computational Geometry, {\bf 36}(1) (2006), 2--15.
\bibitem{aor} Aichholzer, O., Orden, D. and Ramos, P.A., {\it On the structure of sets
    attaining the rectilinear crossing number}, In: Proc. 22nd European
    Workshop on Computational Geometry EuroCG '06, pp. 43--46, Delphi,
    Greece, 2006.
\bibitem{bacher} Bacher, R., {\it Le cocycle du verger}, C. R. Acad. Sci. Paris,
    Ser. I, {\bf 338}(3) (2004), 187--190.
\bibitem{BaGa} Bacher, R. and Garber, D., {\it The Orchard relation
    of planar configurations of points I}, Geombinatorics {\bf 15}(2) (2005), 54--68.
\bibitem{FG} Feder, E. and Garber, D., {\it On the Orchard crossing number of
    complete bipartite graphs}, in preparation.
\bibitem{GPS} Garber, D., Pinchasi, R. and Sharir, M., {\it On some properties of the Orchard
    crossing number of an abstract graph}, in preparation.
\bibitem{PT} Pach, J. and T\'oth, G., {\it Thirteen problems on
    crossing numbers}, Geombinatorics {\bf 9} (2000), 194--207.
\end{thebibliography}

\end{document}


we consider the edges connecting the center and the
vertices of the cycle. These edges can be broken into two subsets.
\begin{enumerate}
\item The edges which meet the cycle only at a vertex of the cycle
(tangent to the cycle). These edges can contribute $0$ to the total
number of crossings.

\item The edges which intersect an edge
of the cycle on route to their vertex. These edges contribute at
least $2$ to the total number of crossings. This is because this
edge separates between two vertices of the cycle, and the edge of
the cycle separates between the two vertices of this edge.
\end{enumerate}

We claim that we can have at most two edges in Subset (1). Assume on
the contrary that there are three such edges (which join the center
$C$ to the vertices $P_1,P_2$ and $P_3$ respectively).
Consider the middle edge. This edge meets the cycle tangentially at
$P_2$, and does not meet the cycle anywhere else. If so, the cycle
should be situated entirely to the right or to the left of this
edge, which is a contradiction.

Hence, we have at most two edges which contribute $0$. This leaves
$n-2$ edges which contribute at least $2$ to the total number of
crossings. We thus have a total of $2n-4$ additional crossings.
For $n \geq 4$, we have $2n-4 \geq n$. Thus in any configuration,
the edges of the cycle contribute at least $n$ crossings. Thus, the
minimality of the configuration of $K_{n,1}$ is preserved when we
add in the cycle to get $W_{n,1}$.

Notice that if we keep the configuration for $K_{n,1}$ (regular $n$-gon
with point in or close to center), but choose a cycle different from
that on the convex hull, we will only increase the number of
crossings. This is because we will then have a self-intersecting
cycle. Each intersection will contribute $2$ crossings. In such a
case the above arguments still apply to add at least $n$ additional
vertices. Thus this configuration has more crossings than when the
cycle is on the convex hull.

\subsection{Complete bipartite graphs of type $K_{n,n}$ - proof of upper bound}


We first compute the number of crossings in the rectilinear drawing that
realizes the $2n$ points of $K_{n,n}$ as the points of a regular $2n$-gon,
and the points change colors alternately.

\begin{rem} \label{num_comp_bipar}
Assume that $R(K_{n,n})$ is the rectilinear drawing of $K_{n,n}$ which
realizes the $2n$ points of $K_{n,n}$ as the points of a regular $2n$-gon,
and the points change colors alternately. Then:
$$n(R(K_{n,n}))= 4n{n \choose 3}$$
\end{rem}

\begin{proof}
Since any quadruple of points is in a convex position,
we have to consider only four types of quadruples:
\begin{enumerate}

\item All the points of the quadruple have the same color.
This case contributes nothing to the number of crossings (see Figure
\ref{bipartite-nn}(a)).

\item The quadruple consists of two black points and two white points,
and the points change colors alternately. This case contributes
nothing to the number of crossings (see Figure
\ref{bipartite-nn}(b)).

\item Three of the points are black and one point is white (or vice versa).
This case contributes $1$ to the number of crossings (see Figure
\ref{bipartite-nn}(c)).

\item The quadruple consists of two consecutive black points followed
by two consecutive white points. This case contributes $2$ to the
number of crossings (see Figure \ref{bipartite-nn}(d)).

\end{enumerate}

\begin{figure}[h]
\epsfysize=2.5cm \centerline{\epsfbox{bipartite-nn.eps}}
\caption{Four cases of quadruples of points in a convex position}
\label{bipartite-nn}
\end{figure}


Hence, we have to count the number of quadruples of types (3) and
(4), and to multiply them by their contributions to the total
numbers of crossings.

For counting the number of quadruples of type (3), we have to choose
three black points out of $n$ black points, and then to choose one
white point. There are $n{n \choose 3}$ possibilities to do so.
Since, we have to do the same with the opposite colors, we have
$2n{n \choose 3}$ quadruples of type (3), which contribute $2n{n
\choose 3}$ to the total number of crossings.

The count of quadruples of type (4) is a bit more complicated. We
count them in the following way: Choose an arbitrary point. Then
choose another point of the same color. Then, choose two points of
opposite color to the left of the second point, but to the right of
the first point. One can easily see that the number of possibilities
is:
$$\frac{2n}{4} \sum_{k=2}^{n-1}k(k-1),$$
where the sum is induced from choosing the second point of the first
color. The division by $4$ comes from the fact that by this counting
argument, each quadruple is counted four times, once for each point
of it.

We simplify this expression:
\begin{eqnarray*}
\frac{2n}{4} \sum_{k=2}^{n-1}k(k-1) & = & \frac{n}{2}
\sum_{k=1}^{n-1}(k^2-k) =\\
& = & \frac{n}{2}\left( \frac{(n-1)n(2n-1)}{6} -
\frac{n(n-1)}{2}\right) =\\
& =& \frac{n \cdot n (n-1)(n-2)}{6}=n{n \choose 3}
\end{eqnarray*}

Hence, we get that the number of quadruples of type (4) is $n{n
\choose 3}$. Since each quadruple of type (4) contributes two
crossings, this number should be multiplied by $2$ for getting the
total contribution of the quadruples of type (4). Hence, the
quadruples of type (4) contribute $2n{n \choose 3}$.

Summing up the two contributions yields the result.
\end{proof}

\subsection{Complete bipartite graphs of type $K_{n,2}$ - wrong proof}

In this section we deal with Orchard crossing number of the complete
bipartite graphs of type $K_{n,2}$.

Assume that we have $n$ black points and two white points. Then, we
have the following result:

\begin{prop}
The configuration of $n+2$ points which yields the minimal number of
Orchard crossings for the graph $K_{n,2}$ consists of $n+2$ points
in a convex position, and the two white points are located in
antipodal position (see Figure \ref{k_m2}).

\begin{figure}[h]
\epsfysize=4cm \centerline{\epsfbox{k_m2.eps}}
\caption{An example of $K_{n,2}$ for $n=6$} \label{k_m2}
\end{figure}


Hence, we have:
$$
{\rm OCN}(K_{n,2})=\left\{
\begin{array}{cl}
            \frac{(n-1)(n-2)(n+1)}{2} &  n\ {\rm odd} \\
            \frac{n^2(n-2)}{2}        &  n\ {\rm even}
\end{array}
\right.
$$

\end{prop}

\begin{proof}
We look on quadruples of points with two black points and two white
points. We have three cases:
\begin{enumerate}
\item Two white points and two black points in a convex position,
alternating in colors (see Figure \ref{bipartite_k_n2}(a)). This
quadruple contributes nothing to the total number of crossings.
\item Two white points and two black points in a convex position,
two black points and then two white points (see Figure
\ref{bipartite_k_n2}(b)). This quadruple contributes $2$ to the
total number of crossings.
\item A black point inside a triangle consists of two white points and
one black point (see Figure \ref{bipartite_k_n2}(c)). This quadruple
also contributes $2$ to the total number of crossings.
\end{enumerate}

\begin{figure}[h]
\epsfysize=3cm \centerline{\epsfbox{bipartite_k_n2.eps}}
\caption{Three cases of quadruples of points with two black points
and two white point} \label{bipartite_k_n2}
\end{figure}

We want to minimize the number of quadruples of types (2) and (3) as
a whole. Let $L$ be the line which connects the two white points.
This line divides the $n$ black points into two subsets - one
contains $k$ points, and the other contains $n-k$ points.

If two black points are located on the same side of $L$, then the
corresponding quadruple (of these two black points and the two whihe
points) is of type (2) or (3) and hence contributes two crossing. We
have ${k \choose 2} + {n-k \choose 2}$ such quadruples.

This number is minimized for $k = \frac{n}{2}$, which means that the
line connecting the two white points divides the black points into
two subsets with the same number of points (or different by 1 if $n$
is even).

For proving that all the points are organized in a convex position,
let us look on quintuples of  points with two white points and three
black points, see Figure \ref{quintuple_k_n2}. The best
configuration is (a) with $4$ crossings (whence drawings (b) and (c)
have $5$ crossings and drawings (d) has $6$ crossings).

\begin{figure}[h]
\epsfysize=3cm \centerline{\epsfbox{quintuple_k_n2.eps}}
\caption{Four generic configurations of $5$ points with two white
points and three black points} \label{quintuple_k_n2}
\end{figure}

Hence, the same argument from $K_n$ will work here too: for having
the minimal number of crossings, we want to have all the quintuples
in a convex position, and this will be satisfied if all the points
are in a convex position as needed.

Now, for computing the number of crossings, we have to split to two
cases: $n$ odd and $n$ even. If $n$ is even, we have $\frac{n}{2}$
black points at each side of the line which connects the two white
points. Since in a quintuple, we have one black point in one side,
and two black points in the other side, we have
$2\frac{n}{2}{\frac{n}{2} \choose 2}$ quintuples (since the "head"
of the quintuple can be at both sides of the line). Such a quintuple
contributes $4$ crossings, so we have:
$${\rm OCN}(K_{n,2}) = 8 \frac{n}{2}{\frac{n}{2} \choose 2}=
4n \frac{\frac{n}{2}\frac{n-2}{2}}{2}=\frac{n^2(n-2)}{2}$$

If $n$ is odd, we have $\frac{n+1}{2}$ black points at one side of
the line which connects the two white points, and $\frac{n-1}{2}$
black points at its other side. As in the even case, we have
$\frac{n-1}{2}{\frac{n+1}{2} \choose 2} +
\frac{n+1}{2}{\frac{n-1}{2} \choose 2}$ quintuples. Such a quintuple
contributes $4$ crossings, so we have:
\begin{eqnarray*}
{\rm OCN}(K_{n,2}) &= & 4 \left( \frac{n-1}{2}{\frac{n+1}{2} \choose
2} + \frac{n+1}{2}{\frac{n-1}{2} \choose 2} \right) = \\
&=& 4 \left( \frac{n-1}{2}\frac{\frac{n+1}{2}\frac{n-1}{2}}{2} +
\frac{n+1}{2}\frac{\frac{n-1}{2}\frac{n-3}{2}}{2} \right) = \\
& =& \frac{(n-1)(n+1)}{2} \left( \frac{n-1}{2} + \frac{n-3}{2}
\right) = \\
&=& \frac{(n-1)(n-2)(n+1)}{2}
\end{eqnarray*}


\end{proof}



\section{The Maximal Orchard crossing number of the cycle $C_n$}

Here, we present a partial result concerning the maximal Orchard
crossing number of a cycle of length $n$, where $n$ is odd.

\begin{prop}
Let $n$ be an odd number. For all cycles of length $n$ on $n$ points
in a convex position, the maximal amount of crossings is
$\frac{n(n-1)(n-3)}{4}$. This amount is achieved in a star drawing.
\end{prop}

\begin{proof}
For a given edge $E$ on the cycle determined by $P$ and $Q$, the
number of separating lines for $P$ and $Q$ can be determined as
follows. Consider the line connecting $P$ and $Q$. This line divides
the remaining $n-2$ points into two subsets of size $k$ and $l$
(corresponding to the two sides of the line). Notice that for two
points $R$ and $S$ in different classes, the line connecting $R$ and
$S$ separates $P$ and $Q$. How many such lines are there? Clearly
$kl$. We know $k + l = n-2$. In order to maximize $k l$, we want $k
= \frac{n-1}{2}$ and $l= \frac{n-3}{2}$. In other words, we want all
lines to split the other points into two almost equal size classes
(difference is $1$ since $n$ is odd). This is accomplished by a
star. To form the star, start from any point. Connect it to a point
$\frac{n-1}{2}$ points clockwise from that point. Iterate until you
arrive back at the original point. (since $n$ and $\frac{n-1}{2}$
are relatively prime, there will not be any repeats and all points
will be hit). Each of the $n$ edges will divide the remaining points
as desired. The number of crossings is therefore
$\frac{n(n-1)(n-3)}{4}$. (there is no repeated counting).
\end{proof}

Note that if some points are inside the convex hull, then $P$ and
$Q$ can be separated by two points on the same side of $E$. This may
result in more crossings.


\section{$MOCN(C_n)$, $n$ even}





This is for the case of n odd  we can form a star relatively simple.
When n is even however, this cannot really be done. If we have one
edge which splits the points in half, the next edge in the cycle
cannot. The question is how to maximize. 2 methods: Method 1. a)pick
a point. b) next point is n/2 points clockwise away c) next is n/2 -
1 away d) next is n/2 away...i) next is n/2 away j) last is 1 away.
(try it to see). Computing the total number of crossings generated,
we get n(n-2)(n-3)/4. This is the method we must use for n = 2(mod
4). Method 2: For n=0(mod 4), we have a better method. a) pick a
point b) next point is n/2 - 1 clockwise points away c) next point
is again n/2 - 1 clockwise points away.... keep going until we hit
the starting point and cover all other points along the way. (for n
= 2(mod 4) we will not cover all points and therefore can't use this
better method). If you compute the total number of crossings we get
$n^2(n-4)/4$, better than method 1 for $n\geq6$. Thus we have
$n^2(n-4)/4$ for n=0(mod 4)  (exception: for n=4, use the number for
n=0(mod 4)) and  n(n-2)(n-3)/4  for  n=2(mod 4).


\subsection{21.1}

To prove my bounds for the max OCN for cycle with pts in convex
position, I can show that it boils down to the following problem-
maybe you know a method to solve.

Choose $k_1, k_2,..., k_n$  in $Z_n$. Want to minimize the following
sum under the following conditions; $\sum_{i=1}^n [n/2 - k_i]^2$

Conditions: Define $p_1,...,p_n$ recursively as follows: Initialize
$p_1 = k_1$. Let $p_i = p_i-1 + k_i$. The conditions on the $k_i$'s
are such that:

1) $p_1 \neq p_2 \neq .... p_n  (mod n)$,  i.e all the $p_i$'s are
different (mod n)

2) $p_n = 0 (mod n)$


Claim: 1) for n odd, sum is minimized for $k_i = (n-1)/2$  for all
$i$ . This I can prove.

2) for $n = 0(mod 4)$,    $k_i = n/2 - 1$ for all $k_i$.

3) for $n = 2(mod 4)$,    $k_1 = n/2, k_2 = n/2 - 1, k_3= n/2, k_4 =
n/2 - 1,..., k_n-2 = n/2 - 1, k_n-1= n/2, k_n = 1$.

Parts 2 and 3 I haven't proven. Do you know how?


\subsection{24.1}

My conjecture for $n=2(mod 4)$ was wrong. I found a better sequence
for the $k_i$'s - hopefully the best. First $n/2 - 1$ k's have value
$n/2 - 1$.   Then one $k$ with value $n/2 -2$.    Then another $n/2
- 1$ k's with value $n/2 - 1$.   Then the last $k = n/2$.   This
sequence of k's meets the criterion and has a higher number of
crossings. It yields $(n^3 - 4n^2 -8)/4$ crossings. Thus my
conjecture now stands at max. number of crossings(orchard) for a
cycle on n points in convex position is: $n(n-1)(n-3)/4$ for $n$ odd
(I can prove), $n^2(n-4)/4$  for $n=0(mod 4)$, $n^2(n-4)/4 - 2$ for
$n = 2(mod 4).$

 First, a series of $n/2 -1$ with value $n/2 - 1$.
Then one of value $n/2$. Then a series of $n/2 - 1$ with value $n/2
+ 1$. Then another of value $n/2$. This leads to $(n^3 -4n^2 + 8) /
4$ crossings. This works for all $n$ even. To take stock of what we
have. max. number of crossings(orchard) for a cycle on n points in
convex position is: for n odd:  $n(n-1)(n-3)/4 = (n^3 - 4n^2 +3n) /
4$ (I can prove) for n even, I have an upper and lower bound for \#
crossings as follows: $$(n^3 -4n^2 +8)/4  \leq \#crossings < (n^3
-4n^2 +2n) / 4$$



To do:

1) check the sequence of MOCN(K_n) and see if appears in OEIS.

2) what happen for union for graphs which are not disjoint.

3) Next, I'll see if I can extend this to the wheel. Can you verify
these for smaller n by computer.

\section{Union in case of non-disjoint}


I think that it will work in the OCN, since the OCN take into
account all the lines generated by ALL the points in the
configurations, and not only the lines correspond to edges. I do not
think it will work in the other crossing number, since there we do
not take into account all the involved lines generated by the
configuration, but it should be checked.

I fear that it will not work in case that G and H have common edges
(since in the proof we use the fact that we delete all the graph of
G or H), and we just have to find a counter-example here). Try two
subgraphs which their union gives $K_4$ or $K_5$.

I think I have a counterexample for RCN. Consider $G= K_{4,1}  H=
K_4 \cup v$, (i.e $K_4$ with an isolated fifth point). Notice
RCN(G)= 0 = RCN(H). The following config. C gives 0 crossings for
both. - four points in convex position, 1 point inside. To see this
for H: $K_4$ can be drawn with 0 crossings by a triangle with a
point inside. Now put the fifth point outside the triangle. for G:
To form $K_{4,1}$, let the fifth point(from H) be the 1 and let the
other 4 be the 4. Clearly, 0 crossings. Notice G and H are disjoint.

Now consider $G \cup H$. Well $G \cup H = K_5$. In config C we have
3 crossings. But $K_5$ can be drawn with one crossing. i.e. triangle
with 2 points in center. (notice also that RCN isn't additive, even
for disjoint graphs, but OCN is).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


3) BTW, finding OCN(K_n,1) can be phrased as:  What is the minimal
possible row sum for all possible n+1 x n+1 separating matrices
corresponding to configs of n+1 points? I'm not sure if this helps
us, but in writing a program, you may be able to use the code from
our work with the matrices.


\section{Previous proof of $K_{n,1}$}

In order to minimize the number of crossings, the best configuration
should include as many as possible quadruples of type (a), and
as few as possible of quadruples of the other types.
This is satisfied by the configuration in the formulation of the proposition,
since it does not have quadruples of type (c) at all.
Putting the white point at the center of the polygon (or close to it, in the even case)
will induce the largest possible number of quadruples of type (a), and the smallest
number of quadruples of type (b).

Now, we have to show two things:
\begin{enumerate}
\item If we take one of the black points inside the polygon (which will induce
a convex hull
of $n-1$ black points), the total number of crossings will increase.
\item Under the assumption that all the $n$ black points are in a convex position,
putting
the white point at the center (or close to it) is the best place with respect to
the total number of crossings.
\end{enumerate}

We start with (1). If we do the simplest move, which pushes one of the black points
into the convex hull of the rest of the black points, we will get that at least one
quadruple of type (b) will be converted into a quadruple of type (c), without changing
anything more, and hence we get an increase in the total
number of crossings. If we iterate
it more, we generate more and more quadruples of type (c) which increase the total
number of crossings.  A similar argument will show that in general
the best configuration for the black points is the convex position.

Now, we explain part (2). We claim that moving the white point from the center
will increase the total number of crossings. This can be shown as follows:
Let $l$ be a line generated by two black points, which bounds one side of the center.
This line divides the set of black points into three subsets: the two points that
generated this line, the set $A$ of points which are in the same side
of $l$ as the center, and the set $B$ of the rest. Clearly, $|A|>|B|$.
Now, when the white point is moved from the center and crosses $l$, we
subtract one crossing for each point in $B$ (since $l$ is not anymore a
separating line), but you have to add one crossing for each point in $A$
(since now $l$ is a separating line). Hence, we have an increase
in the total number of crossings.
A similar argument will show that placing the white
at any other point out of the center will cause an increase
in the total number of crossings.
Hence, the best place for the white point is the center of the polygon (or close to it
in the even case).


We show here a different way for computing the number of crossings
in the rectilinear drawing which yields the minimal number of
crossing:

\begin{prop}
$$
{\rm OCN}(K_{n,1})=\left\{
\begin{array}{cl}
            \frac{n(n-1)(n-3)}{8}  &  n\ {\rm odd} \\
            \frac{n(n-2)^2}{8}     &  n\ {\rm even}
\end{array}
\right.
$$
\end{prop}

\begin{proof}
We count the number of Orchard crossings in the configuration
presented in the last proposition. We split our treatment into two
cases: the odd case and the even case.

In the odd case, we have to compute the number of chords that
separate between the center of that $n$-gon $C$ and a point $P$ on
the $n$-gon (see Figure \ref{k_m1_odd} as an example for $n=7$).

\begin{figure}[h]
\epsfysize=5cm \centerline{\epsfbox{k_m1_odd.eps}} \caption{An
example of $n=7$ for the computation of $K_{n,1}$, where $n$ is odd}
\label{k_m1_odd}
\end{figure}

The point $Q$, just to the right of $P$, is the end point of
$\frac{n-1}{2}-1$ chords that separate $C$ and $P$, since separated
chords have to pass to the left of the center $C$, and there are
exactly $\frac{n-1}{2}-1$ such chords. The next point to the right
$R$, is the end point of $\frac{n-1}{2}-2$ chords that separate $C$
and $P$, since again separated chords have to pass to the left of
the center $C$, and should be connected only to points which are to
the left of the point $P$ (in order to separate $C$ and $P$). By
going over all the possible chords, we get that the total number of
such chords is:
$$\sum _{i=1} ^{\frac{n-1}{2}-1} i = \frac{(n-1)(n-3)}{8}$$
We have to multiply this number by the number of black points, and
hence the result of odd $n$ follows.

\medskip

The even case is more difficult. The chords which connect antipodal
vertices divide the $n$-gon into $n$ triangles. The white point $C$
is located near the center of the $n$-gon in one of these triangles,
which is denoted by $T$ (see Figure \ref{k_m1_even} for an example
of $n=8$).

\begin{figure}[h]
\epsfysize=5cm \centerline{\epsfbox{k_m1_even.eps}} \caption{An
example of $n=8$ for the computation of $K_{n,1}$, where $n$ is
even} \label{k_m1_even}
\end{figure}

As in the odd case, we have computed that the total number of chords
which separate $C$ and the two points of the base of the triangle
$T$ (e.g. points $P_1$ and $P_2$ in Figure \ref{k_m1_even}) is
$$\frac{(n-2)(n-4)}{8}.$$
Now, the points next to these two points (e.g. points $P_3$ and
$P_8$ in Figure \ref{k_m1_even}) have almost the same number of
chords. The difference is an extra chord which is the edge of the
triangle $T$. Hence, the total number of chords that separate $C$
and each one of these two points is:
$$\frac{(n-2)(n-4)}{8}+1.$$
The next two points have one more extra chord, which is generated by
the two previous points and their antipodals, and so on.

Hence, in order to get the Orchard crossing number, we have to sum
over all the points. The result is:
$$2 \sum_{i=0}^{\frac{n}{2}-1} (\frac{(n-2)(n-4)}{8}+i) = \frac{n(n-2)^2}{8}$$
as needed.
\end{proof}

math0303317.extracted_bib
\begin{thebibliography}{99}
\bibitem{AFLS} Abrego, B.M., Fernandez-Merchant, S., Leanos, J. and Salazar, G., {\it The maximum number of halving lines and the rectilinear crossing number of $K_n$ for $n \leq 27$}, Electronic Notes in Discrete Math. {\bf 30} (2008), 261--266.
\bibitem{aak} Aichholzer, O., Aurenhammer, F. and Krasser, H.,
    {\it Enumerating order types for small point sets with
    applications}, in: Proc. 17th Ann. ACM Symp. Computational
    Geometry, 11--18, Medford, Massachusetts, USA, 2001.
\bibitem{aak2} Aichholzer, O., Aurenhammer, F. and Krasser, H.,
    {\it On the crossing number of complete graphs}, in: Proc. 18th
    Ann. ACM Symp. Computational Geometry, 19--24, Barcelona, Spain, 2002.
\bibitem{AGOR} Aichholzer, O., Garcia, J., Orden, D. and Ramos, P., {\it New lower bounds
    for the number of ($\leq k$)-edges and the rectilinear crossing number of $K_n$},
    Discrete Comput. Geom. {\bf 38}(1) (2007), 1--14.
\bibitem{ak} Aichholzer, O. and Krasser, H., {\it The point set order
    type data base: A collection of applications and results}, in: Proc. 13th
    Annual Canadian Conference on Computational Geometry CCCG 2001,
    17--20, Waterloo, Ontario, Canada, 2001.
\bibitem{ak2} Aichholzer, O. and Krasser, H., {\it Abstract order type extension and
    new results on the rectilinear crossing number}, Computational
    Geometry: Theory and Applications, Special Issue on the 21st
    European Workshop on Computational Geometry, {\bf 36}(1) (2006), 2--15.
\bibitem{aor} Aichholzer, O., Orden, D. and Ramos, P.A., {\it On the structure of sets
    attaining the rectilinear crossing number}, In: Proc. 22nd European
    Workshop on Computational Geometry EuroCG '06, pp. 43--46, Delphi,
    Greece, 2006.
\bibitem{bacher} Bacher, R., {\it Le cocycle du verger}, C. R. Acad. Sci. Paris,
    Ser. I, {\bf 338}(3) (2004), 187--190.
\bibitem{BaGa} Bacher, R. and Garber, D., {\it The Orchard relation
    of planar configurations of points I}, Geombinatorics {\bf 15}(2) (2005), 54--68.
\bibitem{FG} Feder, E. and Garber, D., {\it On the Orchard crossing number of
    complete bipartite graphs}, in preparation.
\bibitem{GPS} Garber, D., Pinchasi, R. and Sharir, M., {\it On some properties of the Orchard
    crossing number of an abstract graph}, in preparation.
\bibitem{PT} Pach, J. and T\'oth, G., {\it Thirteen problems on
    crossing numbers}, Geombinatorics {\bf 9} (2000), 194--207.
\end{thebibliography}