Name
Abstract | ||
|---|---|---|
An axis-parallel b-dimensional box is a Cartesian product R1×R2×⋯×Rb where each Ri (for 1≤i≤b) is a closed interval of the form [ai,bi] on the real line. The boxicity of any graph G, box(G) is the minimum positive integer b such that G can be represented as the intersection graph of axis-parallel b-dimensional boxes. A b-dimensional cube is a Cartesian product R1×R2×⋯×Rb, where each Ri (for 1≤i≤b) is a closed interval of the form [ai,ai+1] on the real line. When the boxes are restricted to be axis-parallel cubes in b-dimension, the minimum dimension b required to represent the graph is called the cubicity of the graph (denoted by cub(G)). In this paper we prove that cub(G)≤⌈log2n⌉box(G), where n is the number of vertices in the graph. We also show that this upper bound is tight. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.disc.2008.04.011 | Discrete Mathematics |
Keywords | Field | DocType |
Cubicity,Boxicity,Interval graph,Indifference graph | Discrete mathematics,Indifference graph,Combinatorics,Interval graph,Cartesian product,Boxicity,Chordal graph,Intersection graph,Treewidth,Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
309 | 8 | 0012-365X |
Citations | PageRank | References |
9 | 0.63 | 16 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| L. Sunil Chandran | 1 | 552 | 54.01 |
| K. Ashik Mathew | 2 | 12 | 1.75 |