Skip to main content
Notice removed Draw attention by CommunityBot
Bounty Ended with no winning answer by CommunityBot
added 60 characters in body
Source Link
Michael Hardy
  • 1
  • 12
  • 85
  • 126

Suppose $G$ is a graph embedded in the plane with $m=|E(G)|$ edges and $n=|V(G)|$ vertices. Suppose $sim(G)$$\operatorname{sim}(G)$, the simplification of $G$ contains $ m' >> 3n $$ 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 $sim(G)$$\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 $sim(G)$$\operatorname{sim}(G)$ the set $U$ of edges $e \in sim(G)$$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

Suppose $G$ is a graph embedded in the plane with $m=|E(G)|$ edges and $n=|V(G)|$ vertices. Suppose $sim(G)$, the simplification of $G$ contains $ m' >> 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 $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 $sim(G)$ the set $U$ of edges $e \in 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

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

added 22 characters in body
Source Link
Hao S
  • 111
  • 2
  • 11

Suppose $G$ is a graph embedded in the plane with $m=|E(G)|$ edges and $n=|V(G)|$ vertices. Suppose $sim(G)$, the simplification of $G$ contains $ m' >> 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 $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 $sim(G)$ the set $U$ of edges $e \in 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

Suppose $G$ is a graph with $m=|E(G)|$ edges and $n=|V(G)|$ vertices. Suppose $sim(G)$, the simplification of $G$ contains $ m' >> 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 $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 $sim(G)$ the set $U$ of edges $e \in 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

Suppose $G$ is a graph embedded in the plane with $m=|E(G)|$ edges and $n=|V(G)|$ vertices. Suppose $sim(G)$, the simplification of $G$ contains $ m' >> 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 $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 $sim(G)$ the set $U$ of edges $e \in 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

added 113 characters in body
Source Link
Hao S
  • 111
  • 2
  • 11

Suppose $G$ is a graph with $m=|E(G)|$ edges and $n=|V(G)|$ vertices. Suppose $sim(G)$, the simplification of $G$ contains $ m' >> 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 $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 $sim(G)$ the set $U$ of edges $e \in 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

Suppose $G$ is a graph with $m=|E(G)|$ edges and $n=|V(G)|$ vertices. Suppose $sim(G)$, the simplification of $G$ contains $ m' >> 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 $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 $sim(G)$ the set $U$ of edges $e \in 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|$?

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

Suppose $G$ is a graph with $m=|E(G)|$ edges and $n=|V(G)|$ vertices. Suppose $sim(G)$, the simplification of $G$ contains $ m' >> 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 $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 $sim(G)$ the set $U$ of edges $e \in 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

Notice added Draw attention by Hao S
Bounty Started worth 50 reputation by Hao S
added 11 characters in body
Source Link
Hao S
  • 111
  • 2
  • 11
Loading
Source Link
Hao S
  • 111
  • 2
  • 11
Loading