A Repository of Graph Algorithms
Manufactured by: Debajyoti Mondal
Graph Drawing Coloring Combinatorics
Graph Drawing Coloring Geometry Combinatorics

## My Favourite Open Problems

Under Construction :)

• Graph Coloring and Combinatorics
1. Does there exist a geometric thickness 2 graph with 6n-18 edges, where n is the number of vertices?
2. Does there exist a graph with geometric thickness 2 that is not 8 colorable?
3. Determine the minimum integer d such that every geometric thickness 2 graph contains a vertex of degree at most d.
4. What is the complexity of acyclic k-coloring for (planar) graphs with maximum degree k, where k ∈ {3,4}?
5. Can every 3-connected cubic graph with more than 8 vertices be colored acyclically with 3-colors?
6. What is the minimum constant ck such that every n-vertex planar graph admits a 1-subdivision with at most nck division vertices that is acyclically k-colorable (where k=3 or k=4)?
• Graph Drawing
1. Does every n-vertex planar triangulation admit a 1-bend polyline drawing with (4/3-ε)Δ slopes?
2. Does every n-vertex planar triangulation admit a 1-bend point-set embedding on n points (on the Euclidean plane) in general position?
3. Does every 3-connected cubic graph admits a greedy embedding in polynomial area?
4. Is there a linear-time algorithm for breaking all separating triangles of a planar graph?
5. What is the complexity of one sided crossing minimization, where each vertex on the free side has degree at most three?
6. Find an efficient algorithm to test whether a plane 3-tree of n vertices admits a 1-bend point-set embedding on a set of n points, i.e., each edge can have at most one bend point.
7. Does every n-vertex planar graph admit a polyline drawing with (3/8)n^2 area (variable embedding setting) and bend complexity two?
8. 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.
9. Does polyline drawings allow us to achieve better upper bound (smaller than 2.33n) on the number of segments while drawing planar triangulations?
10. Does every planar triangulation admit a straight-line drawing with O(n^{2+ε}) area and \Omega(1/n^ε) angular resolution, where ε is a constant in the interval (0,1)?
11. Does every thickness-3 graph admit a thickness-3 polyline drawing with o(√n) bends per edge?