Geometric representation of graphs in low dimension
<|reference_start|>Geometric representation of graphs in low dimension: We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in $1.5 (\Delta + 2) \ln n$ dimensions, where $\Delta$ is the maximum degree of G. We also show that $\boxi(G) \le (\Delta + 2) \ln n$ for any graph G. Our bound is tight up to a factor of $\ln n$. 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 $c\cdot(d_{av} + 1) \ln n$ where d_{av} is the average degree and c is a small constant. Also, we show that for any graph G, $\boxi(G) \le \sqrt{8 n d_{av} \ln n}$, which is tight up to a factor of $b \sqrt{\ln n}$ for a constant b.<|reference_end|>
@article{chandran2006geometric,
    title={Geometric representation of graphs in low dimension},
    author={L. Sunil Chandran and Mathew C Francis and Naveen Sivadasan},
    journal={arXiv preprint arXiv:cs/0605013},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0605013},
    primaryClass={cs.DM cs.DS}
}