Separation dimension of sparse graphs

MaRDI QIDQ6250813zbMATH OpenFDO

Authors Manu Basavaraju, L. Sunil Chandran, Rogers Mathew, Deepak Rajendraprasad

Publication date 17 April 2014

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: The separation dimension of a graph $G$ is the smallest natural number $k$ for which the vertices of $G$ can be embedded in $mathbb{R}^k$ such that any pair of disjoint edges in $G$ can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family $mathcalF$ of permutations of the vertices of $G$ such that for any two disjoint edges of $G$, there exists at least one permutation in $mathcalF$ in which all the vertices in one edge precede those in the other. In general, the maximum separation dimension of a graph on $n$ vertices is $Theta(logn)$. In this article, we focus on sparse graphs and show that the maximum separation dimension of a $k$-degenerate graph on $n$ vertices is $O(kloglogn)$ and that there exists a family of $2$-degenerate graphs with separation dimension $Omega(loglogn)$. We also show that the separation dimension of the graph $G^{1/2}$ obtained by subdividing once every edge of another graph $G$ is at most $(1+o(1))loglogchi(G)$ where $chi(G)$ is the chromatic number of the original graph.

This page was built for publication: Separation dimension of sparse graphs

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