Timeline for Proofs of theorems that proved more or deeper results than what was first supposed or stated as the corresponding theorem
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 9, 2021 at 19:16 | comment | added | Patrick Lutz | @lambda The paper you linked to appears to be the paper where they prove there is a $O(\log^3(n))$ amortized time algorithm for fully-dynamic planarity testing. The paper linked to in the other answer that talks about this appears to be the paper from earlier in 2019 which contained the key ideas that led to the later result. | |
| Mar 9, 2021 at 19:14 | comment | added | Patrick Lutz | (continued from previous comment) But in 2019, Holm and Rotenberg gave an algorithm that takes $$O(\log^3(n))$$ time per insertion/deletion on average. So an exponential speed up over the best previously known algorithm. Apparently much of the idea for this result was already present in a paper that they had written earlier in 2019. I think this Quanta article has a better explanation of this result than the article linked in the answer above. | |
| Mar 9, 2021 at 19:11 | comment | added | Patrick Lutz | As far as I can tell, here's what this is about. Suppose you have a graph which is being gradually updated: at any point in time edges may be added or removed from the graph (but the vertex set stays fixed). You want to know at each point in time whether the current graph is planar. This problem is apparently called "fully-dynamic planarity testing." Before 2019, the best known algorithm took O(sqrt(n)) time per edge insertion/deletion on average (where n is the number of vertices in the graph). (continued in next comment) | |
| Mar 8, 2021 at 6:05 | comment | added | lambda | That article doesn't really say anything about what the result actually was, other than involving planar graphs somehow. The actual paper is at arxiv.org/abs/1911.03449 (linked in the article, but I went and found it myself before noticing that). Maybe someone familiar with the problem could add some context. | |
| Mar 7, 2021 at 23:15 | review | First posts | |||
| Mar 8, 2021 at 4:24 | |||||
| S Mar 7, 2021 at 23:15 | history | answered | Atnas | CC BY-SA 4.0 | |
| S Mar 7, 2021 at 23:15 | history | made wiki | Post Made Community Wiki by Atnas |