Geometric representation of graphs in low dimension
| dc.creator | Chandran, L. Sunil | |
| dc.creator | Francis, Mathew C | |
| dc.creator | Sivadasan, Naveen | |
| dc.date | 2006-05-04 | |
| dc.date | 2007-07-31 | |
| dc.date.accessioned | 2026-07-07T08:21:10Z | |
| dc.date.available | 2026-07-07T08:21:10Z | |
| dc.description | We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in $1.5 (Δ+ 2) \ln n$ dimensions, where $Δ$ is the maximum degree of G. We also show that $\boxi(G) \le (Δ+ 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 $Δ$, 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. | |
| dc.description | preliminary version appeared in Cocoon 2006 | |
| dc.identifier | https://arxiv.org/abs/cs/0605013 | |
| dc.identifier | http://arxiv.org/abs/cs/0605013 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/135274 | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Geometric representation of graphs in low dimension | |
| dc.type | text |