An upper bound for Cubicity in terms of Boxicity |
| |
Authors: | L. Sunil Chandran K. Ashik Mathew |
| |
Affiliation: | Department of Computer Science and Automation, Indian Institute of Science, Bangalore-560012, India |
| |
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, 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 ). In this paper we prove that , where n is the number of vertices in the graph. We also show that this upper bound is tight.Some immediate consequences of the above result are listed below: - 1.
- Planar graphs have cubicity at most 3⌈log2n⌉.
- 2.
- Outer planar graphs have cubicity at most 2⌈log2n⌉.
- 3.
- Any graph of treewidth tw has cubicity at most (tw+2)⌈log2n⌉. Thus, chordal graphs have cubicity at most (ω+1)⌈log2n⌉ and circular arc graphs have cubicity at most (2ω+1)⌈log2n⌉, where ω is the clique number.
The above upper bounds are tight, but for small constant factors. |
| |
Keywords: | Cubicity Boxicity Interval graph Indifference graph |
本文献已被 ScienceDirect 等数据库收录! |
|