- Does the class of constant-degree expanders have polynomially-long induced paths?
- Planar embedding conjecture — Can every planar graph equipped with an arbitrary shortest-path metric be embedded into L1 with only a constant distortion? Anastasios Sidiropoulos solves the case when the metric has non-positive curvature; Chekuri et al. proves the case when the graph is O(1)-outerplanar; Chakrabarti et al. proves a natural analogous case when the graph is (K5-e)-free.
- Barnette conjecture (not the one about Hamiltonian cycle) — There is always non-null-homotopic separating simple cycle on every triangulation of an orientable surface of genus g greater than 3.