Separation dimension of bounded degree graphs

DOI10.1137/140973013zbMATH Open1327.05245arXiv1407.5075OpenAlexW2133883172MaRDI QIDQ3453564FDOQ3453564

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)

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$.

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

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

zbMATH Keywords

boxicitybounded degreeseparation dimensionlinegraph

Mathematics Subject Classification ID

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

Cited In (13)

• Circular separation dimension of a subclass of planar graphs
• The induced separation dimension of a graph
• Separation dimension of graphs and hypergraphs
• Separation dimension and degree
• Fractional and circular separation dimension of graphs
• Separation numbers of trees
• 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
• Separation dimension and sparsity

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)