Problem related to crossing number

Question

Let $G$ be a graph embedded in the plane (with crossings). For $ F \subset E(G) $, denote by $c(F)$ the set of edges of $G$ that cross some edge in $F$. Denote $\delta(v)$ the set of edges with one endpoint in $v$. For a node $v \in G $, denote $ d(v) = \min \{|F| + | \delta(v) \setminus c(F) |\colon F \subseteq E(G) \} $ the size of the smallest set of edges such that each edge leaving $v$ is either contained in or crosses an edge of this set.

Can we bound $ \sum_{v \in G} d(v) $ in terms of $V(G)$?

What if $G$ is bipartite?

This is somewhat motivated by optimization in generalizations of planar graphs.

Answer 1

Here we prove $$\sum_{v \in V} d(v) = O(|V(G)|^{3/2}).$$ Let $n = |V(G)|$. We can find an $F$ such that $|F| = O(n^{1/2})$ and $|E(G) \backslash c(F)| \leq n^{3/2}$. To achieve this, we consider the following algorithm:

1. Add the edge $e$ of $G$ intersecting the most edges to $F$.
2. Remove from $G$ all edges intersecting $e$.
3. Repeat until $G$ has at most $n^{3/2}$ edges.

By the crossin inequality, as long as $G$ has $m \geq n^{3/2}$ edges, the number of pairs of edges crossing each other is at least $m^3 / 64 n^2$, which implies that some edge $e$ crosses $m^2 / 64 n^2$ other edges. Thus, if $m_i$ is the number of edges in $G$ after step $i$ of the algorithm, we have $$m_{i + 1} \leq m_i - \frac{m_i^2}{64n^2}.$$ Let $i_k$ be the largest $i$ such that $m_i \leq 2^k n^{3/2}$. Then for any $i \leq i_k$, we have $$m_{i + 1} \leq m_i - 2^{2k} n / 64$$ which gives $$m_{i_{k - 1} + 1} \geq m_{i_k + 1} + 2^{2k} (i_{k - 1} - i_k) \cdot 2^{2k} n / 64.$$ But we have $m_{i_{k - 1} + 1} \leq 2^{k + 1} n^{3 / 2}$, so we have $$i_{k - 1} - i_k \leq 64 \cdot 2^{-k} n^{1/2}.$$ Telescoping, we conclude that $i_0 = O(n^{1/2})$. So at the end of the algorithm, we have $|F| = O(n^{1/2})$ as desired.

With this $F$, we have $$d(v) \leq |F| + |\delta(v) \backslash c(F)|.$$ Summing over all $v$, we have $$\sum_{v \in V} d(v) \leq n|F| + 2 |\{\text{edges not crossing $F$}\}| = O(n^{3/2}).$$