Boxicity

<h2 id="examples">Examples</h2>
The figure shows a graph with six vertices, and a representation of this graph as an intersection graph of rectangles (two-dimensional boxes). This graph cannot be represented as an intersection graph of boxes in any lower dimension, so its boxicity is two.
Roberts (1969) showed that the graph with 2n vertices formed by removing a <a href="/facts/Perfect_matching/LmtRYLgK">perfect matching</a> from a <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> on 2n vertices has boxicity exactly n: each pair of disconnected vertices must be represented by boxes that are separated in a different dimension than each other pair. A box representation of this graph with dimension exactly n can be found by thickening each of the 2n facets of an n-dimensional <a href="/facts/Hypercube/q2mRPbIz">hypercube</a> into a box. Because of these results, this graph has been called the Roberts graph,<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> although it is better known as the cocktail party graph and it can also be understood as the <a href="/facts/Tur%25C3%25A1n_graph/y0hzJqQQ">Turán graph</a> T(2n,n).

<h2 id="relation-to-other-graph-classes">Relation to other graph classes</h2>
A graph has boxicity at most one if and only if it is an <a href="/facts/Interval_graph/oLwYI3uT">interval graph</a>; the boxicity of an arbitrary graph G is the minimum number of interval graphs on the same set of vertices such that the intersection of the edges sets of the interval graphs is G. Every <a href="/facts/Outerplanar_graph/FrAgUpcV">outerplanar graph</a> has boxicity at most two,<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> and every <a href="/facts/Planar_graph/plREagr9">planar graph</a> has boxicity at most three.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>
If a <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite graph</a> has boxicity two, it can be represented as an intersection graph of axis-parallel line segments in the plane.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
Adiga, Bhowmick & Chandran (2011) proved that the boxicity of a bipartite graph G is within of a factor 2 of the <a href="/facts/Order_dimension/JaFXu3WE">order dimension</a> of the height-two <a href="/facts/Partially_ordered_set/qb4a3FAX">partially ordered set</a> associated to G as follows: the set of minimal elements corresponds to one partite set of G, the set of maximal elements corresponds to the second partite set of G, and two elements are comparable if the corresponding vertices are adjacent in G. Equivalently, the <a href="/facts/Order_dimension/JaFXu3WE">order dimension</a> of a height-two <a href="/facts/Partially_ordered_set/qb4a3FAX">partially ordered set</a> P is within a factor 2 of the boxicity of the <a href="/facts/Comparability_graph/dLht35EJ">comparability graph</a> of P (which is bipartite, since P has height two).

<h2 id="algorithmic-results">Algorithmic results</h2>
Many graph problems can be solved or approximated more efficiently for graphs with bounded boxicity than they can for other graphs; for instance, the <a href="/facts/Maximum_clique_problem/cVVBNP08">maximum clique problem</a> can be solved in polynomial time for graphs with bounded boxicity.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> For some other graph problems, an efficient solution or approximation can be found if a low-dimensional box representation is known.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> However, finding such a representation may be difficult:
it is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a> to test whether the boxicity of a given graph is at most some given value K, even for K = 2.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>
Chandran, Francis & Sivadasan (2010) describe algorithms for finding representations of arbitrary graphs as intersection graphs of boxes, with a dimension that is within a <a href="/facts/Logarithm/QeXaV97q">logarithmic</a> factor of the <a href="/facts/Degree_(graph_theory)/LnFFpI8v">maximum degree</a> of the graph; this result provides an upper bound on the graph's boxicity.
Despite being hard for its natural parameter, boxicity is <a href="/facts/Parameterized_complexity/RoyaJGgJ">fixed-parameter tractable</a> when parameterized by the <a href="/facts/Vertex_cover/WK86bJvf">vertex cover</a> number of the input graph.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

<h2 id="bounds">Bounds</h2>
If a graph G has <a href="/facts/Treewidth/uoITxzRJ">treewidth</a> tw, then:

box
 ⁡
 (
 G
 )
 ≤
 
 t
 w
 
 +
 2
 
 
 {\displaystyle \operatorname {box} (G)\leq \mathrm {tw} +2}
 
.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>
If a graph G has m edges, then:

box
 ⁡
 (
 G
 )
 =
 O
 (
 
 
 m
 ⋅
 log
 ⁡
 (
 m
 )
 
 
 )
 
 
 {\displaystyle \operatorname {box} (G)=O({\sqrt {m\cdot \log(m)}})}
 
.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a><a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>
If a graph G is k-<a href="/facts/Degeneracy_(graph_theory)/IaYkus22">degenerate</a> (with 
 
 
 
 k
 ≥
 2
 
 
 {\displaystyle k\geq 2}
 
) and has n vertices, then G has boxicity 
 
 
 
 box
 ⁡
 (
 G
 )
 ≤
 (
 k
 +
 2
 )
 ⌈
 2
 e
 log
 ⁡
 n
 ⌉
 
 
 {\displaystyle \operatorname {box} (G)\leq (k+2)\lceil 2e\log n\rceil }
 
.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>
If a graph G has no complete graph on t vertices as a <a href="/facts/Graph_minor/qn5eI22T">minor</a>, then 
 
 
 
 box
 ⁡
 (
 G
 )
 =
 O
 (
 
 t
 
 2
 
 
 log
 ⁡
 t
 )
 
 
 {\displaystyle \operatorname {box} (G)=O(t^{2}\log t)}
 
<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> while there are graphs with no complete graph on t vertices as a <a href="/facts/Graph_minor/qn5eI22T">minor</a>, and with boxicity 
 
 
 
 Ω
 (
 t
 
 
 log
 ⁡
 t
 
 
 )
 
 
 {\displaystyle \Omega (t{\sqrt {\log t}})}
 
.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> In particular, any graph G has boxicity 
 
 
 
 box
 ⁡
 (
 G
 )
 =
 O
 (
 μ
 (
 G
 
 )
 
 2
 
 
 log
 ⁡
 μ
 (
 G
 )
 )
 
 
 {\displaystyle \operatorname {box} (G)=O(\mu (G)^{2}\log \mu (G))}
 
, where 
 
 
 
 μ
 (
 G
 )
 
 
 {\displaystyle \mu (G)}
 
 denotes the <a href="/facts/Colin_de_Verdi%25C3%25A8re_graph_invariant/7DKynAon">Colin de Verdière invariant</a> of G.

<h2 id="related-graph-invariants">Related graph invariants</h2>
<ul><li><a href="/facts/Cubicity/G5TBKpbE">Cubicity</a> is defined in the same way as boxicity but with axis-parallel <a href="/facts/Hypercube/q2mRPbIz">hypercubes</a> instead of hyperrectangles. Boxicity is a generalization of cubicity.</li>
<li><a href="/facts/Sphericity_(graph_theory)/JopnAN9E">Sphericity</a> is defined in the same way as boxicity but with unit-diameter spheres.</li></ul>

<h2 id="notes">Notes</h2>

<ul><li>Adiga, Abhijin; Bhowmick, Diptendu; Chandran, L. Sunil (2011), "Boxicity and Poset Dimension", SIAM Journal on Discrete Mathematics, 25 (4): 1687–1698, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1003.2357">1003.2357</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F100786290">10.1137/100786290</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:12656133">12656133</a>.</li>
<li>Adiga, Abhijin; Chandran, L. Sunil; Mathew, Rogers (2014), "Cubicity, Degeneracy, and Crossing Number", European Journal of Combinatorics, 35: 2–12, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1105.5225">1105.5225</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.ejc.2013.06.021">10.1016/j.ejc.2013.06.021</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:2069078">2069078</a>.</li>
<li>Adiga, Abhijin; Chitnis, Rajesh; Saurabh, Saket (2010), "Parameterized algorithms for boxicity", <a href="https://web.archive.org/web/20170830050212/http://www.wisdom.weizmann.ac.il/~chitnis/fptBoxicity.pdf">Algorithms and Computation: 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I</a> (PDF), Lecture Notes in Computer Science, vol. 6506, pp. 366–377, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-642-17517-6_33">10.1007/978-3-642-17517-6_33</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-642-17516-9, archived from <a href="http://www.wisdom.weizmann.ac.il/~chitnis/fptBoxicity.pdf">the original</a> (PDF) on 2017-08-30, retrieved 2018-01-22</li>
<li><a href="/facts/Pankaj_K._Agarwal/DgAt5H5U">Agarwal, Pankaj K.</a>; van Kreveld, Marc; <a href="/facts/Subhash_Suri/urBqFdWy">Suri, Subhash</a> (1998), "Label placement by maximum independent set in rectangles", <a href="/facts/Computational_Geometry_(journal)/yr5agn50">Computational Geometry Theory and Applications</a>, 11 (3–4): 209–218, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0925-7721%2898%2900028-5">10.1016/S0925-7721(98)00028-5</a>, <a href="/facts/Hdl_(identifier)/rdebSxmC">hdl</a>:<a href="https://hdl.handle.net/1874%2F18908">1874/18908</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:2381363">2381363</a>.</li>
<li>Bellantoni, Stephen J.; Ben-Arroyo Hartman, Irith; <a href="/facts/Teresa_Przytycka/W80gBhSP">Przytycka, Teresa</a>; <a href="/facts/Sue_Whitesides/9Xl4cuNd">Whitesides, Sue</a> (1993), "Grid intersection graphs and boxicity", <a href="/facts/Discrete_Mathematics_(journal)/K4e6z8wQ">Discrete Mathematics</a>, 114 (1–3): 41–49, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0012-365X%2893%2990354-V">10.1016/0012-365X(93)90354-V</a>.</li>
<li>Berman, Piotr; DasGupta, B.; <a href="/facts/S._Muthukrishnan_(computer_scientist)/wRAwYkw3">Muthukrishnan, S.</a>; Ramaswami, S. (2001), "Efficient approximation algorithms for tiling and packing problems with rectangles", J. Algorithms, 41 (2): 443–470, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1006%2Fjagm.2001.1188">10.1006/jagm.2001.1188</a>.</li>
<li>Chandran, L. Sunil; Francis, Mathew C.; Sivadasan, Naveen (2010), "Geometric representation of graphs in low dimension using axis parallel boxes", Algorithmica, 56 (2): 129–140, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/cs.DM/0605013">cs.DM/0605013</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs00453-008-9163-5">10.1007/s00453-008-9163-5</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2576537">2576537</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:17838951">17838951</a>.</li>
<li>Chandran, L. Sunil; Sivadasan, Naveen (2007), "Boxicity and treewidth", <a href="/facts/Journal_of_Combinatorial_Theory/oYS6G76K">Journal of Combinatorial Theory</a>, <a href="/facts/Series_B/a8L5q9kA">Series B</a>, 97 (5): 733–744, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/math.CO/0505544">math.CO/0505544</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.jctb.2006.12.004">10.1016/j.jctb.2006.12.004</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:9854207">9854207</a>.</li>
<li>Chlebík, Miroslav; <a href="/facts/Janka_Chleb%25C3%25ADkov%25C3%25A1/vQY60msu">Chlebíková, Janka</a> (2005), <a href="http://portal.acm.org/citation.cfm?id=1070470">"Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes"</a>, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, pp. 267–276, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-89871-585-9.</li>
<li>Cozzens, M. B. (1981), Higher and Multidimensional Analogues of Interval Graphs, Ph.D. thesis, Rutgers University.</li>
<li>Esperet, Louis (2016), "Boxicity and topological invariants", European Journal of Combinatorics, 51: 495–499, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1503.05765">1503.05765</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.ejc.2015.07.020">10.1016/j.ejc.2015.07.020</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:5548385">5548385</a>.</li>
<li>Esperet, Louis; Wiechert, Veit (2018), <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p51">"Boxicity, poset dimension, and excluded minors"</a>, Electronic Journal of Combinatorics, 25 (4): #P4.51, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1804.00850">1804.00850</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.37236%2F7787">10.37236/7787</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:119148637">119148637</a>.</li>
<li><a href="/facts/Jan_Kratochv%25C3%25ADl/BQ5Has54">Kratochvil, Jan</a> (1994), "A special planar satisfiability problem and a consequence of its NP–completeness", Discrete Applied Mathematics, 52 (3): 233–252, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0166-218X%2894%2990143-0">10.1016/0166-218X(94)90143-0</a>.</li>
<li>Quest, M.; Wegner, G. (1990), "Characterization of the graphs with boxicity ≤ 2", Discrete Mathematics, 81 (2): 187–192, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0012-365X%2890%2990151-7">10.1016/0012-365X(90)90151-7</a>.</li>
<li><a href="/facts/Fred_S._Roberts/Ql0DSQJk">Roberts, F. S.</a> (1969), "On the boxicity and cubicity of a graph", in <a href="/facts/W._T._Tutte/8VbfbzU6">Tutte, W. T.</a> (ed.), <a href="https://archive.org/download/boxicity/boxicity.pdf">Recent Progress in Combinatorics</a> (PDF), Academic Press, pp. 301–310, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-12-705150-5.</li>
<li><a href="/facts/Ed_Scheinerman/sL2UfJug">Scheinerman, E. R.</a> (1984), <a href="https://archive.org/details/intersection-classes-and-multi">Intersection Classes and Multiple Intersection Parameters</a>, Ph. D thesis, Princeton University.</li>
<li><a href="/facts/Carsten_Thomassen_(mathematician)/RSxh10q0">Thomassen, Carsten</a> (1986), "Interval representations of planar graphs", Journal of Combinatorial Theory, Series B, 40: 9–20, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0095-8956%2886%2990061-4">10.1016/0095-8956(86)90061-4</a>.</li>
<li><a href="/facts/Mihalis_Yannakakis/sEHPDT9v">Yannakakis, Mihalis</a> (1982), "The complexity of the partial order dimension problem", SIAM Journal on Algebraic and Discrete Methods, 3 (3): 351–358, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F0603036">10.1137/0603036</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">E.g., see Chandran, Francis & Sivadasan (2010) and Chandran & Sivadasan (2007). - Chandran, L. Sunil; Francis, Mathew C.; Sivadasan, Naveen (2010), "Geometric representation of graphs in low dimension using axis parallel boxes", Algorithmica, 56 (2): 129–140, arXiv:cs.DM/0605013, doi:10.1007/s00453-008-9163-5, MR 2576537, S2CID 17838951 <a href="https://arxiv.org/abs/cs.DM/0605013" target="_blank">https://arxiv.org/abs/cs.DM/0605013</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Scheinerman (1984). - Scheinerman, E. R. (1984), Intersection Classes and Multiple Intersection Parameters, Ph. D thesis, Princeton University <a href="https://archive.org/details/intersection-classes-and-multi" target="_blank">https://archive.org/details/intersection-classes-and-multi</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Thomassen (1986). - Thomassen, Carsten (1986), "Interval representations of planar graphs", Journal of Combinatorial Theory, Series B, 40: 9–20, doi:10.1016/0095-8956(86)90061-4 <a href="https://doi.org/10.1016%2F0095-8956%2886%2990061-4" target="_blank">https://doi.org/10.1016%2F0095-8956%2886%2990061-4</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Bellantoni et al. (1993). - Bellantoni, Stephen J.; Ben-Arroyo Hartman, Irith; Przytycka, Teresa; Whitesides, Sue (1993), "Grid intersection graphs and boxicity", Discrete Mathematics, 114 (1–3): 41–49, doi:10.1016/0012-365X(93)90354-V <a href="https://doi.org/10.1016%2F0012-365X%2893%2990354-V" target="_blank">https://doi.org/10.1016%2F0012-365X%2893%2990354-V</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Chandran, Francis & Sivadasan (2010) observe that this follows from the fact that these graphs have a polynomial number of maximal cliques, i.e., the class of graphs with bounded boxicity is said to have few cliques. An explicit box representation is not needed to list all maximal cliques efficiently. - Chandran, L. Sunil; Francis, Mathew C.; Sivadasan, Naveen (2010), "Geometric representation of graphs in low dimension using axis parallel boxes", Algorithmica, 56 (2): 129–140, arXiv:cs.DM/0605013, doi:10.1007/s00453-008-9163-5, MR 2576537, S2CID 17838951 <a href="https://arxiv.org/abs/cs.DM/0605013" target="_blank">https://arxiv.org/abs/cs.DM/0605013</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">See, e.g., Agarwal, van Kreveld & Suri (1998) and Berman et al. (2001) for approximations to the maximum independent set for intersection graphs of rectangles, and Chlebík & Chlebíková (2005) for results on hardness of approximation of these problems in higher dimensions. - Agarwal, Pankaj K.; van Kreveld, Marc; Suri, Subhash (1998), "Label placement by maximum independent set in rectangles", Computational Geometry Theory and Applications, 11 (3–4): 209–218, doi:10.1016/S0925-7721(98)00028-5, hdl:1874/18908, S2CID 2381363 <a href="https://doi.org/10.1016%2FS0925-7721%2898%2900028-5" target="_blank">https://doi.org/10.1016%2FS0925-7721%2898%2900028-5</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Cozzens (1981) shows that computing the boxicity is NP-complete; Yannakakis (1982) shows that even checking whether the boxicity is at most 3 is NP-hard; finally Kratochvil (1994) showed that recognising boxicity 2 is NP-hard. - Cozzens, M. B. (1981), Higher and Multidimensional Analogues of Interval Graphs, Ph.D. thesis, Rutgers University <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Adiga, Chitnis & Saurabh (2010). - Adiga, Abhijin; Chitnis, Rajesh; Saurabh, Saket (2010), "Parameterized algorithms for boxicity", Algorithms and Computation: 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I (PDF), Lecture Notes in Computer Science, vol. 6506, pp. 366–377, doi:10.1007/978-3-642-17517-6_33, ISBN 978-3-642-17516-9, archived from the original (PDF) on 2017-08-30, retrieved 2018-01-22 <a href="https://web.archive.org/web/20170830050212/http://www.wisdom.weizmann.ac.il/~chitnis/fptBoxicity.pdf" target="_blank">https://web.archive.org/web/20170830050212/http://www.wisdom.weizmann.ac.il/~chitnis/fptBoxicity.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Chandran & Sivadasan (2007, Theorem 14) - Chandran, L. Sunil; Sivadasan, Naveen (2007), "Boxicity and treewidth", Journal of Combinatorial Theory, Series B, 97 (5): 733–744, arXiv:math.CO/0505544, doi:10.1016/j.jctb.2006.12.004, S2CID 9854207 <a href="https://arxiv.org/abs/math.CO/0505544" target="_blank">https://arxiv.org/abs/math.CO/0505544</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Chandran, Francis & Sivadasan (2010) - Chandran, L. Sunil; Francis, Mathew C.; Sivadasan, Naveen (2010), "Geometric representation of graphs in low dimension using axis parallel boxes", Algorithmica, 56 (2): 129–140, arXiv:cs.DM/0605013, doi:10.1007/s00453-008-9163-5, MR 2576537, S2CID 17838951 <a href="https://arxiv.org/abs/cs.DM/0605013" target="_blank">https://arxiv.org/abs/cs.DM/0605013</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Esperet (2016) - Esperet, Louis (2016), "Boxicity and topological invariants", European Journal of Combinatorics, 51: 495–499, arXiv:1503.05765, doi:10.1016/j.ejc.2015.07.020, S2CID 5548385 <a href="https://arxiv.org/abs/1503.05765" target="_blank">https://arxiv.org/abs/1503.05765</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Adiga, Chandran & Mathew (2014) - Adiga, Abhijin; Chandran, L. Sunil; Mathew, Rogers (2014), "Cubicity, Degeneracy, and Crossing Number", European Journal of Combinatorics, 35: 2–12, arXiv:1105.5225, doi:10.1016/j.ejc.2013.06.021, S2CID 2069078 <a href="https://arxiv.org/abs/1105.5225" target="_blank">https://arxiv.org/abs/1105.5225</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Esperet & Wiechert (2018) - Esperet, Louis; Wiechert, Veit (2018), "Boxicity, poset dimension, and excluded minors", Electronic Journal of Combinatorics, 25 (4): #P4.51, arXiv:1804.00850, doi:10.37236/7787, S2CID 119148637 <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p51" target="_blank">http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p51</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Esperet (2016) - Esperet, Louis (2016), "Boxicity and topological invariants", European Journal of Combinatorics, 51: 495–499, arXiv:1503.05765, doi:10.1016/j.ejc.2015.07.020, S2CID 5548385 <a href="https://arxiv.org/abs/1503.05765" target="_blank">https://arxiv.org/abs/1503.05765</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
</ol>

Boxicity open-in-new

Boxicity