Boxicity
Algorithmic results
Algorithmic results
-------------------

Many graph problems can be solved or approximated more efficiently for graphs with bounded boxicity than they can for other graphs; for instance, the [maximum clique problem](/wiki/Maximum_clique_problem "Maximum clique problem") can be solved in polynomial time for graphs with bounded boxicity. observe that this follows from the fact that these graphs have a polynomial number of [maximal cliques](/wiki/Maximal_clique "Maximal clique"), i.e., the class of graphs with bounded boxicity is said to have [few cliques.](/wiki/Graphs_with_few_cliques "Graphs with few cliques") An explicit box representation is not needed to list all maximal cliques efficiently. For some other graph problems, an efficient solution or approximation can be found if a low\-dimensional box representation is known.See, e.g.,  and  for approximations to the [maximum independent set](/wiki/Maximum_independent_set "Maximum independent set") for intersection graphs of rectangles, and  for results on hardness of approximation of these problems in higher dimensions. However, finding such a representation may be difficult:
it is [NP\-complete](/wiki/NP-complete "NP-complete") to test whether the boxicity of a given graph is at most some given value *K*, even for *K* \= 2\. shows that computing the boxicity is NP\-complete;  shows that even checking whether the boxicity is at most 3 is NP\-hard; finally  showed that recognising boxicity 2 is NP\-hard.
 describe algorithms for finding representations of arbitrary graphs as intersection graphs of boxes, with a dimension that is within a [logarithmic](/wiki/Logarithm "Logarithm") factor of the [maximum degree](/wiki/Degree_%28graph_theory%29 "Degree (graph theory)") of the graph; this result provides an upper bound on the graph's boxicity.

Despite being hard for its natural parameter, boxicity is [fixed\-parameter tractable](/wiki/Parameterized_complexity "Parameterized complexity") when parameterized by the [vertex cover](/wiki/Vertex_cover "Vertex cover") number of the input graph..


How does boxicity relate to other graph parameters like chromatic number or treewidth?