Separation dimension of bounded degree graphs

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

Research output: Contribution to journalArticle

6 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 - Jan 1 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

    Alon, N., Basavaraju, M., Chandran, L. S., Mathew, R., & Rajendraprasad, D. (2015). Separation dimension of bounded degree graphs. SIAM Journal on Discrete Mathematics, 29(1), 59-64. https://doi.org/10.1137/140973013