Doing some random readings, also trying to revive the blog :(
- Conjecture [Thomas]. For any t, any sufficiently large t-connected graph with no
-minor can be made planar by removing exactly t-5 vertices.
The case when t=6 has been proven. [Kawarabayashi-Norine-Thomas-Wollan ’12] - In a subgraph-closed graph family, having polynomial expansion is equivalent to having sublinear separator. [Dvořák-Norine ’15]
- Richter-Thomassen Conjecture, now Pach-Rubin-Tardos Theorem, states that the total number of intersections between n pairwise intersecting Jordan curves in the plane, no three pass through the same point, is at least
.
Main Theorem [Pach-Rubin-Tardos ’15]. Consider the above set of Jordan curves. Then the number of crossing points istimes the number of touching points, those that are the only intersection between two Jordan curves.
- Further results on arc and bar k-visibility graphs by Sawhney and Weed, 2016.
- Minimum cut of directed planar graphs in O(n log log n) time by Mozes, Nikolaev, Nussbaum, and Weimann, 2015.
- The weakly simple polygon result has been extended to geometric intersection numbers. [Despré-Lazarus ’15]
Advertisements
