This thesis mainly focuses on algorithmic and combinatorial questions related to some geometric problems on graphs. In the last part of this thesis, a graph coloring problem is also discussed. Boxicity and Cubicity: These ...

Conjectured in 1943, Hadwiger’s conjecture is one of the most challenging open problems in graph theory. Hadwiger’s conjecture states that if the chromatic number of a graph G is k, then G has a clique minor of size at ...