Separation dimension of bounded degree graphs

DOI10.1137/140973013MaRDI QIDQ3453564zbMATH OpenOpenAlexFDO

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

Publication date 27 November 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

bounded degreeboxicitylinegraphseparation dimension

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 total orders of the vertices of $G$ such that for any two disjoint edges of $G$, there exists at least one total order 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 bounded degree graphs and show that the separation dimension of a graph with maximum degree $d$ is at most $2^{9lo{g}^{star}d}d$. We also demonstrate that the above bound is nearly tight by showing that, for every $d$, almost all $d$-regular graphs have separation dimension at least $lceild/2ceil$.

Recommendations

• Separation dimension and degree
• Separation dimension and sparsity
• Separation dimension of graphs and hypergraphs
• Fractional and circular separation dimension of graphs
• Boxicity and separation dimension

Cited in

(15)

• Fractional and circular separation dimension of graphs
• Local boxicity and maximum degree
• Boxicity and separation dimension
• Separation dimension of graphs and hypergraphs
• Induced separation dimension
• Separation dimension and sparsity
• Circular separation dimension of a subclass of planar graphs
• Separation dimension and degree
• Zarankiewicz's problem for semilinear hypergraphs
• Bounds for the decomposition dimension of some class of graphs
• Perfect and nearly perfect separation dimension of complete and random graphs
• Boxicity and cubicity of a subclass of divisor graphs and power graphs of cyclic groups
• A survey on the boxicity and cubicity of graphs
• The induced separation dimension of a graph
• Separation numbers of trees

This page was built for publication: Separation dimension of bounded degree graphs

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