Separation dimension of bounded degree graphs

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

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

The separation dimension of a graph G is the smallest natural number k for which the vertices of G can be embedded in Rk 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 29 log ∗ 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 ⌈d/2⌉.

Original languageEnglish (US)
Pages (from-to)59-64
Number of pages6
JournalSIAM Journal on Discrete Mathematics
Volume29
Issue number1
DOIs
StatePublished - 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Bounded degree
  • Boxicity
  • Linegraph
  • Separation dimension

Fingerprint

Dive into the research topics of 'Separation dimension of bounded degree graphs'. Together they form a unique fingerprint.

Cite this