Timeline for "separators" for nonplanar graphs embedded in the plane
Current License: CC BY-SA 4.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 14 at 6:12 | comment | added | Hao S | @SaúlRM edited question | |
| Jun 14 at 6:11 | history | edited | Hao S | CC BY-SA 4.0 |
added 13 characters in body
|
| Jun 13 at 15:33 | comment | added | Saúl RM | @HaoS Could you edit the question to include the condition that by "small set of edges" you mean $o(V(G))$ edges? I was thinking of sharing this question but as it is now, one needs to read the comments to understand the question | |
| S Jun 9 at 0:08 | history | bounty ended | CommunityBot | ||
| S Jun 9 at 0:08 | history | notice removed | CommunityBot | ||
| Jun 5 at 16:16 | comment | added | Hao S | @IlyaBogdanov the planar separator theorem | |
| Jun 5 at 12:43 | comment | added | Ilya Bogdanov | So is it true that such set of order $O(\sqrt{V(G)})$ (or at least $o(V(G))$) exists for any planar graph? | |
| S May 31 at 22:08 | history | bounty started | Hao S | ||
| S May 31 at 22:08 | history | notice added | Hao S | Draw attention | |
| Mar 29 at 18:36 | comment | added | Hao S | Ah yes forget I said $ o(\sqrt(V(G)))$ lets just say $o(V(G)) $ | |
| Mar 29 at 9:28 | comment | added | Louis Esperet | Sorry I meant $\Omega(\sqrt{|V(G)|})$ ! In your comment above you speculated that $o(\sqrt{|V(G)|})$ could be possible. | |
| Mar 27 at 21:51 | comment | added | Hao S | @LouisEsperet, doesn't just taking a path from the middle node of the top to the middle node of the bottom plus a few more edges work? Can you draw your example? | |
| Mar 27 at 16:04 | comment | added | Louis Esperet | 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). | |
| Mar 25 at 3:55 | comment | added | Tony Huynh | Ah, I see. The question makes sense to me now. | |
| Mar 24 at 21:38 | comment | added | Hao S | @TonyHuynh My definition of separator is different it is, the removal of all edges that intersect or share an endpoint of an edge of $S$, In laymens terms, I remove the region of the plane occupied by edges of $S$ It's not clear that a complete graph doesn't have this kind of "separator" | |
| Mar 24 at 21:09 | comment | added | Tony Huynh | @HaoS My point is that the complete graphs do not have sublinear separators (according to your definition). | |
| Mar 22 at 18:08 | comment | added | Hao S | @TonyHuynh I don't the problem is not about embedding it's about separators. | |
| Mar 22 at 4:35 | comment | added | Tony Huynh | You probably also want to bound the number of crossings, or have some other assumption like $k$-planarity. Otherwise, every graph can be drawn in the plane with crossings. | |
| Mar 22 at 4:13 | history | edited | Hao S | CC BY-SA 4.0 |
added 30 characters in body
|
| Mar 22 at 4:05 | comment | added | Salvo Tringali | Something is missing in your last sentence. Maybe "is planar"? | |
| Mar 22 at 1:25 | comment | added | Hao S | @MoisheKohan o(|V(G)) or even say o( $\sqrt |V(G)| $ ) | |
| Mar 22 at 0:36 | comment | added | Moishe Kohan | What is "small" and what is the question? | |
| Mar 21 at 23:30 | history | asked | Hao S | CC BY-SA 4.0 |