Geometric Representation of Graphs in Low Dimension

DOI10.1007/11809678_42MaRDI QIDQ3591333zbMATH OpenOpenAlexFDO

Authors L. Sunil Chandran, Naveen Sivadasan

Publication date 10 September 2007

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

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

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

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.

Recommendations

• Geometric representation of graphs in low dimension using axis parallel boxes
• Boxicity and maximum degree
• Boxicity and treewidth
• Sublinear approximation algorithms for boxicity and related problems
• Lower bounds for boxicity

Cited in

(17)

• Boxicity of graphs with bounded degree
• Sublinear approximation algorithms for boxicity and related problems
• Local boxicity
• Representability and boxicity of simplicial complexes
• Boxicity and maximum degree
• Parameterized algorithms for boxicity
• On the Cubicity of Interval Graphs
• The frame dimension and the complete overlap dimension of a graph
• Boxicity of line graphs
• p-box: a new graph model
• Geometric Representation of High Dimension, Low Sample Size Data
• On Minimizing One Dimension of Some Two-Dimensional Geometric Representations of Plane Graphs
• A note on lower bounds for boxicity of graphs
• Grid intersection graphs and boxicity
• A note on maximum independent set and related problems on box graphs
• Geometric representation of graphs in low dimension using axis parallel boxes
• 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)