2008/10/30 by Diptendu Bhowmick, Bhowmick, Diptendu, L. Sunil Chandran +1 · 1 citation
Computer Science · Mathematics · #05C62 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #math.CO #msc:05C62
paper · pdf · doi:10.48550/arxiv.0810.5524
18 pages
openalex publication_date 2008/10/30 · arxiv created 2008/12/04 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A k-dimensional box is the cartesian product R1 × R2 × ... × Rk where each Ri is a closed interval on the real line. The \it boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes: that is two vertices are adjacent if and only if their corresponding boxes intersect. A circular arc graph is a graph that can be represented as the intersection graph of arcs on a circle. Let G be a circular arc graph with maximum degree Δ. We show that if Δ<\lfloor (n(α-1))/(2α)\rfloor, α∈ ℕ, α≥ 2 then box(G) ≤ α. We also demonstrate a graph with boxicity > α but with Δ=n((α-1))/(2α)+(n)/(2α(α+1))+(α+2). So the result cannot be improved substantially when α is large. Let rinf be minimum number of arcs passing through any point on the circle with respect to some circular arc representation of G. We also show that for any circular arc graph G, box(G) ≤ rinf + 1 and this bound is tight. Given a family of arcs F on the circle, the circular cover number L(F) is the cardinality of the smallest subset F' of F such that the arcs in F' can cover the circle. Maximum circular cover number Lmax(G) is defined as the maximum value of L(F) obtained over all possible family of arcs F that can represent G. We will show that if G is a circular arc graph with Lmax(G)> 4 then box(G) ≤ 3.