Geometric Representation of Graphs in Low Dimension

DOI10.1007/11809678_42zbMATH Open1162.05338arXivcs/0605013OpenAlexW1869392848MaRDI QIDQ3591333

Naveen Sivadasan, L. Sunil Chandran

Publication date: 10 September 2007

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in $1.5(Delta+2)lnn$ dimensions, where $Delta$ is the maximum degree of G. We also show that $$ for any graph G. Our bound is tight up to a factor of $lnn$. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree $Delta$, we show that for almost all graphs on n vertices, its boxicity is upper bound by $ccdot(d_{av}+1)lnn$ where d_{av} is the average degree and c is a small constant. Also, we show that for any graph G, $$, which is tight up to a factor of $bsqrtlnn$ for a constant b.

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

Mathematics Subject Classification ID

Could not fetch data.

Related Items (2)

On the Cubicity of Interval Graphs ⋮ Minimal Euclidean representations of graphs

This page was built for publication: Geometric Representation of Graphs in Low Dimension

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