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.
16
-
$\begingroup$ What is "small" and what is the question? $\endgroup$– Moishe KohanCommented Mar 22 at 0:36
-
$\begingroup$ @MoisheKohan o(|V(G)) or even say o( $\sqrt |V(G)| $ ) $\endgroup$– Hao SCommented Mar 22 at 1:25
-
$\begingroup$ Something is missing in your last sentence. Maybe "is planar"? $\endgroup$– Salvo TringaliCommented Mar 22 at 4:05
-
1$\begingroup$ You won't be able to beat $\Omega(|V(G)|)$ (take a grid and add an edge between two vertices at distance 4, which are not on the same face, in order to make it non planar). $\endgroup$– Louis EsperetCommented Mar 27 at 16:04
-
1$\begingroup$ @SaúlRM edited question $\endgroup$– Hao SCommented Jun 14 at 6:12
|
Show 11 more comments