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

boxicitybounded degreeseparation dimensionlinegraph

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

(13)

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

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)