On the cubicity of bipartite graphs

DOI10.1016/J.IPL.2008.12.020zbMATH Open1209.68358arXiv0810.2697OpenAlexW2079047321MaRDI QIDQ987780FDOQ987780

Authors: L. Sunil Chandran, Anita Das, Naveen Sivadasan 

Publication date: 16 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: {it A unit cube in $k$-dimension (or a $k$-cube) is defined as 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 of the form $[a_i,a_i+1]$. The {it cubicity} of $G$, denoted as $cub(G)$, is the minimum $k$ such that $G$ is the intersection graph of a collection of $k$-cubes. Many NP-complete graph problems can be solved efficiently or have good approximation ratios in graphs of low cubicity. In most of these cases the first step is to get a low dimensional cube representation of the given graph. It is known that for a graph $G$, $cub(G)leqlfloorfrac2n3floor$. Recently it has been shown that for a graph $G$, $cub(G)leq4(Delta+1)lnn$, where $n$ and $Delta$ are the number of vertices and maximum degree of $G$, respectively. In this paper, we show that for a bipartite graph $G=(AcupB,E)$ with $|A|=n_1$, $|B|=n_2$, $n_{1}leq{n}_2$, and $Delt{a}^{\prime }=minDelt{a}_A,Delt{a}_B$, where $Delt{a}_A={max}_{ainA}d(a)$ and $Delt{a}_B={max}_{binB}d(b)$, $d(a)$ and $d(b)$ being the degree of $a$ and $b$ in $G$ respectively, $cub(G)leq2(Delt{a}^{\prime }+2)lceilln{n}_{2}ceil$. We also give an efficient randomized algorithm to construct the cube representation of $G$ in $3(Delt{a}^{\prime }+2)lceilln{n}_{2}ceil$ dimensions. The reader may note that in general $Delt{a}^{\prime }$ can be much smaller than $Delta$.}

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

Recommendations

• Cubicity and bandwidth
• The cubicity of hypercube graphs
• On the Cubicity of Interval Graphs
• Cubicity, boxicity, and vertex cover
• On the cubicity of interval graphs

zbMATH Keywords

algorithmsintersection graphscubicity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Cites Work

• The Complexity of the Partial Order Dimension Problem
• A special planar satisfiability problem and a consequence of its NP- completeness
• Title not available (Why is that?)
• Grid intersection graphs and boxicity
• Geometric representation of graphs in low dimension using axis parallel boxes
• The cubicity of hypercube graphs
• On the cubicity of certain graphs
• A characterization of Robert's inequality for boxicity
• Sphericity exceeds cubicity for almost all complete bipartite graphs
• Sphericity, cubicity, and edge clique covers of graphs

Cited In (8)

• On the dimer problem of the vertex-edge graph of a cubic graph
• A new invariant of plane bipartite cubic graphs
• Irreducible pseudo 2-factor isomorphic cubic bipartite graphs
• Title not available (Why is that?)
• Cubicity and bandwidth
• Maximum bipartite subgraphs of cubic triangle-free planar graphs
• On the cubicity of AT-free graphs and circular-arc graphs
• On partial cubes, well-graded families and their duals with some applications in graphs

This page was built for publication: On the cubicity of bipartite graphs

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