My Favourite Open Problems
Under Construction :)

Graph Coloring and Combinatorics

Does there exist a geometric thickness 2 graph with 6n18 edges, where n is the number of vertices?

Does there exist a graph with geometric thickness 2 that is not 8 colorable?

Determine the minimum integer d such that every geometric thickness 2 graph
contains a vertex of degree at most d.

What is the complexity of acyclic kcoloring for (planar) graphs with maximum degree k, where k ∈ {3,4}?

Can every 3connected cubic graph with more than 8 vertices be colored acyclically with 3colors?

What is the minimum constant c_{k} such that every nvertex planar graph admits a
1subdivision with at most nc_{k} division vertices that is acyclically kcolorable (where k=3 or k=4)?

Graph Drawing

Does every nvertex planar triangulation admit a 1bend polyline drawing with (4/3ε)Δ slopes?

Does every nvertex planar triangulation admit a 1bend pointset embedding on n points (on the Euclidean plane) in general position?

Does every 3connected cubic graph admits a greedy embedding in polynomial area?

Is there a lineartime algorithm for breaking all separating triangles of a planar graph?

What is the complexity of one sided crossing minimization, where each vertex on the free side has degree at most three?

Find an efficient algorithm to test whether a plane 3tree of n vertices admits a 1bend pointset embedding on a set of n points,
i.e., each edge can have at most one bend point.

Does every nvertex planar graph admit a polyline drawing with (3/8)n^2 area (variable
embedding setting) and bend complexity two?

Determine the minimum integer b (both in fixed and variable embedding settings) such that the
area upper bound cannot be improved by allowing a bend complexity higher than b.

Does polyline drawings allow us to achieve better upper bound (smaller than 2.33n)
on the number of segments while drawing planar triangulations?

Does every planar triangulation admit a
straightline drawing with O(n^{2+ε}) area and \Omega(1/n^ε) angular resolution, where
ε is a constant in the interval (0,1)?

Does every thickness3 graph admit a thickness3 polyline drawing with o(√n) bends per edge?