On the intersection of edges of a geometric graph by straight lines (Q1080859)

A geometric graph \((=gg)\) is a pair \(G=<V,E>\), where V is a finite set of points \((=\) vertices) in general position in the plane and E is a set of open straight line segments \((=\) edges) whose endpoints are in V. For \(S\subseteq R^ 2\), denote by I(G,S) the number of edges of G that intersect S. Denote by I(G,m) the maximum of I(G,M) where M range over all unions of m straight lines in \(R^ 2\). For \(n\geq 1\), \(0\leq e\leq \left( \begin{matrix} n\\ 2\end{matrix} \right)\) and \(m\geq 1\) define \(I(n,e,m)=\min \{I(G,m)|\) G is a gg with n vertices and e edges\(\}\). Define \(I_ c(n,e,m)\) similarly with G also required to be \(convex.\) I\({}_ c(n,e,m)\) is explicitly determined for all n, e and m and it is shown that \(I(n,cn+1,1)=c^ 2+c+1\) provided \(n=\lfloor n/2c\rfloor (2c+2)\). This last result partially settles a conjecture of \textit{P. Erdős, L. Lovász, A. Simmons} and \textit{E. G. Straus} [Survey combin. Theory, Sympos. Colorado State Univ., Colorado 1971, 139-149 (1973; Zbl 0258.05112)]. The following particularly interesting lemma is used to obtain a lower bound for I(n,e,m). Let V be a set of n points in general position in the plane and suppose \(n=\sum^{2m}_{i=1}n_ i\), where \(n_ i\) are nonnegative integers. Then there exist m lines \(\ell_ 1,\ell_ 2,...,\ell_ m\subseteq R^ 2\setminus V\) and a partition of V into 2m pairwise disjoint subsets \(V_ 1,V_ 2,...,V_{2m}\), such that \(| V_ i| =n_ i\) and every two distinct subsets \(V_ i\) and \(V_ j\) are separated by at least one of the m lines.