2014/07/18 by Noga Alon, Alon, Noga, Manu Basavaraju +7
Computer Science · Mathematics · #05C62 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · doi:10.48550/arxiv.1407.5075
openalex publication_date 2014/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The 'separation dimension' of a graph G is the smallest natural number k for which the vertices of G can be embedded in ℝ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 F 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 F 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 Θ(log n). 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^9log⋆ 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 \lceil d/2\rceil.