Boxicity of circular arc graphs

DOI10.1007/S00373-010-1002-1MaRDI QIDQ659754zbMATH OpenOpenAlexFDO

Authors Diptendu Bhowmick, L. Sunil Chandran

Publication date 24 January 2012

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0810.5524

zbMATH Keywords

boxicitycircular arc graph

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Abstract: A $k$-dimensional box is the cartesian product $R_{1}imes{R}_{2}imes\mathrm{...}imes{R}_k$ where each $R_i$ 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 $Delta$. We show that if $Delta<lfloorfracn(alpha-1)2alphafloor$, $alphainmathbbN$, $alphageq2$ then $box(G)leqalpha$. We also demonstrate a graph with boxicity $>alpha$ but with $Delta=nfrac(alpha-1)2alpha+fracn2alpha(alpha+1)+(alpha+2)$. So the result cannot be improved substantially when $alpha$ is large. Let $r_{inf}$ 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)leq{r}_{inf}+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^{\prime }$ of $F$ such that the arcs in $F^{\prime }$ can cover the circle. Maximum circular cover number $L_{max}(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 $L_{max}(G)>4$ then $box(G)leq3$.

Recommendations

• A constant factor approximation algorithm for boxicity of circular arc graphs
• A constant factor approximation algorithm for boxicity of circular arc graphs
• Boxicity of graphs with bounded degree
• Partial characterizations of circular-arc graphs
• Partial Characterizations of Circular-Arc Graphs
• Boxicity of Halin graphs
• Boxicity of line graphs
• On some subclasses of circular-arc graphs
• Circular‐arc digraphs: A characterization
• Boxicity of graphs on surfaces

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3737705 (Why is no real title available?)
• scientific article; zbMATH DE number 3566474 (Why is no real title available?)
• A special planar satisfiability problem and a consequence of its NP- completeness
• Boxicity and maximum degree
• Boxicity and treewidth
• Boxicity of graphs with bounded degree
• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Coloring a Family of Circular Arcs
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• Cubicity, boxicity, and vertex cover
• Geometric representation of graphs in low dimension using axis parallel boxes
• Hadwiger's conjecture for proper circular arc graphs
• Interval bigraphs and circular arc graphs
• Interval representations of planar graphs
• Powers of cycles, powers of paths, and distance graphs
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Stability in circular arc graphs
• Structure theorems for some circular-arc graphs
• The Complexity of the Partial Order Dimension Problem
• The clique operator on circular-arc graphs
• Unit Circular-Arc Graph Representations and Feasible Circulations

Cited in

(6)

• Boxicity of leaf powers
• A constant factor approximation algorithm for boxicity of circular arc graphs
• A constant factor approximation algorithm for boxicity of circular arc graphs
• Chronological rectangle digraphs which are two-terminal series-parallel
• Boxicity of line graphs
• Normal Helly circular-arc graphs and its subclasses

This page was built for publication: Boxicity of circular arc graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q659754)