1
$\begingroup$

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)$?

Is anything stronger possible if $G$ is bipartite?

This is somewhat motivated by optimization in generalizations of planar graphs. Also posted here https://math.stackexchange.com/questions/4923574/problem-related-to-crossing-number/4925180#4925180

$\endgroup$

0

You must log in to answer this question.