Computer Science – Discrete Mathematics
Scientific paper
2006-05-04
Computer Science
Discrete Mathematics
preliminary version appeared in Cocoon 2006
Scientific paper
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.
Chandran Sunil L.
Francis Mathew C.
Sivadasan Naveen
No associations
LandOfFree
Geometric representation of graphs in low dimension does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Geometric representation of graphs in low dimension, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Geometric representation of graphs in low dimension will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-299754