Skip to main content
added 13 characters in body
Source Link
Hao S
  • 111
  • 2
  • 11

Given a nonplanar graph $G$ drawn in the plane with crossings. Does there exist a small ($o(|V(G)|$) subset $S$ of edges of $G$ such that after the removal of all edges that intersect or share an endpoint of an edge of $S$, each component of the remaining graph has at most $\frac{2}{3}|V(G)|$ vertices.

Given a nonplanar graph $G$ drawn in the plane with crossings. Does there exist a small subset $S$ of edges of $G$ such that after the removal of all edges that intersect or share an endpoint of an edge of $S$, each component of the remaining graph has at most $\frac{2}{3}|V(G)|$ vertices.

Given a nonplanar graph $G$ drawn in the plane with crossings. Does there exist a small ($o(|V(G)|$) subset $S$ of edges of $G$ such that after the removal of all edges that intersect or share an endpoint of an edge of $S$, each component of the remaining graph has at most $\frac{2}{3}|V(G)|$ vertices.

Notice removed Draw attention by CommunityBot
Bounty Ended with no winning answer by CommunityBot
Notice added Draw attention by Hao S
Bounty Started worth 50 reputation by Hao S
added 30 characters in body
Source Link
Hao S
  • 111
  • 2
  • 11

Given a nonplanar graph $G$ drawn in the plane with crossings. Does there exist a small subset $S$ of edges of $G$ such that after the removal of all edges that intersect or share an endpoint of an edge of $S$, each component of the remaining graph has at most $\frac{2}{3}|V(G)|$ vertices.

Given a nonplanar graph $G$ drawn in the plane with crossings. Does there exist a small subset $S$ of edges of $G$ such that after the removal of all edges that intersect or share an endpoint of an edge of $S$, each component of the remaining graph

Given a nonplanar graph $G$ drawn in the plane with crossings. Does there exist a small subset $S$ of edges of $G$ such that after the removal of all edges that intersect or share an endpoint of an edge of $S$, each component of the remaining graph has at most $\frac{2}{3}|V(G)|$ vertices.

Source Link
Hao S
  • 111
  • 2
  • 11

"separators" for nonplanar graphs embedded in the plane

Given a nonplanar graph $G$ drawn in the plane with crossings. Does there exist a small subset $S$ of edges of $G$ such that after the removal of all edges that intersect or share an endpoint of an edge of $S$, each component of the remaining graph