Abhijin Adiga
ABSTRACT
We show that every graph of maximum degree 3 can be represented as the intersection graph of axis parallel boxes in three dimensions, that is, every vertex can be mapped to an axis parallel box such that two boxes intersect if and only if their corresponding vertices are adjacent. In fact, we construct a representation in which any two intersecting boxes just touch at their boundaries. Further, this construction can be realized in linear time.
- A. Adiga, D. Bhowmick, L. S. Chandran, Boxicity and poset dimension., SIAM J. Discrete Math. 25 (4) (2011) 1687--1698. Google Scholar
Digital Library
- A. Adiga, L. S. Chandran, Representing a cubic graph as the intersection graph of axis-parallel boxes in three dimensions, archived version of this paper. http://arxiv.org/abs/1108.5635.Google Scholar
- L. S. Chandran, M. C. Francis, N. Sivadasan, Boxicity and maximum degree. J. Comb. Theory Ser. B 98 (2) (2008) 443--445. Google ScholarDigital Library
- L. Esperet, Boxicity of graphs with bounded degree, European J. Combin. 30 (5) (2009) 1277--1280. Google ScholarDigital Library
- S. Felsner, M. C. Francis, Contact representations of planar graphs with cubes. in: Proc. 27th Annu. ACM Sympos. Comput. Geom. (SoCG 2011), 2011. Google ScholarDigital Library
- F. S. Roberts, Recent Progresses in Combinatorics, chap. On the boxicity and cubicity of a graph, Academic Press, New York, 1969, pp. 301--310.Google Scholar
- E. R. Scheinerman, Intersection classes and multiple intersection parameters. Ph.D. thesis, Princeton University (1984).Google Scholar
- E. R. Scheinerman, D. B. West, The interval number of a planar graph: Three intervals suffice, J. Comb. Theory Ser. B 35 (1983) 224--239.Google ScholarCross Ref
- C. Thomassen, Interval representations of planar graphs, J. Comb. Theory Ser. 40 (1986) 9--20. Google ScholarDigital Library
Index Terms
- Representing a cubic graph as the intersection graph of axis-parallel boxes in three dimensions
Recommendations
Representing a Cubic Graph as the Intersection Graph of Axis-Parallel Boxes in Three Dimensions
We show that every graph of maximum degree 3 can be represented as the intersection graph of axis parallel boxes in three dimensions, that is, every vertex can be mapped to an axis parallel box such that two boxes intersect if and only if their ...
Boxicity of Halin graphs
A k-dimensional box is the Cartesian product R"1xR"2x...xR"k where each R"i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G) is the minimum integer k such that G is the intersection graph of a collection of k-...
Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes
An axis-parallel k-dimensional box is a Cartesian product R1 R2 źźź Rk where Ri (for 1≤i≤k) is a closed interval of the form [ai,bi] on the real line. For a graph G, its boxicity boxź(G) is the minimum dimension k, such that G is representable as the ...
Comments