1
$\begingroup$

Suppose $G$ is a graph embedded in the plane with $m=|E(G)|$ edges and $n=|V(G)|$ vertices. Suppose $\operatorname{sim}(G)$, the simplification of $G$ contains $ m' \gg 3n $ edges.
Call the set of edges corresponding to an edge $uv$ of $G$ the parallel set $p(uv)$ of $uv$. What is the maximum $r$ such that for some set $ W $ of edges of $\operatorname{sim}(G)$ the set $U$ of edges $e$ such that each edge of $p(e)$ is intersected by some edge of $p(f)$ for some $f \in W$ has size at least $r|W|$?

What is the maximum $r$ such that for some set $ W $ of vertices of $\operatorname{sim}(G)$ the set $U$ of edges $e \in \operatorname{sim}(G)$ such that each edge of $p(e)$ is intersected by some edge of $p(f)$ for some edge $f$ with at least one endpoint in $W$ has size at least $r|W|$?

Colloquially is crossing each edge of a parallel set much harder than crossing an edge of the simplification?

I found some stuff here but it has requirements on embedding https://arxiv.org/pdf/1801.00721.pdf

Improve this question
$\endgroup$
4
  • $\begingroup$ I am not sure about the specific questions asked here, but in general without further assumptions, the best you can say about the crossing lemma for multigraphs is to simply apply the lemma to the simplification, as you can always draw parallel edges that are close to each other. $\endgroup$
    – Hung-Hsun Yu
    Commented Apr 7 at 4:12
  • $\begingroup$ @Hung-HsunYu I'm not sure what you mean by "the best you can say about the crossing lemma for multigraphs is to simply apply the lemma to the simplification" what does it say here? $\endgroup$
    – Hao S
    Commented May 2 at 16:35
  • $\begingroup$ @Hung-HsunYu: I think the OP is assuming the multigraph comes with a chosen embedding from the start. // @ OP, it would be very helpful to clarify this — is $G$ embedded from the start, or if not, where/how are you quantifying over possible embeddings? $\endgroup$
    – Peter LeFanu Lumsdaine
    Commented May 2 at 17:27
  • $\begingroup$ @PeterLeFanuLumsdaine Yes there is a fixed embedding of G. $\endgroup$
    – Hao S
    Commented May 2 at 18:05

0

Reset to default

You must log in to answer this question.