{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:36:34Z","timestamp":1787322994888,"version":"build-2736575974"},"reference-count":15,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>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 $\\mathcal{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 $\\mathcal{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 $\\Theta(\\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^{9{log^{\\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 $\\ceil{d\/2}$.<\/jats:p>","DOI":"10.1137\/140973013","type":"journal-article","created":{"date-parts":[[2015,1,6]],"date-time":"2015-01-06T12:26:18Z","timestamp":1420547178000},"page":"59-64","source":"Crossref","is-referenced-by-count":11,"title":["Separation Dimension of Bounded Degree Graphs"],"prefix":"10.1137","volume":"29","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manu","family":"Basavaraju","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"L. Sunil","family":"Chandran","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rogers","family":"Mathew","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Deepak","family":"Rajendraprasad","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,1,6]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020303"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"N. Alon and J. H. Spencer,\n                      The Probabilistic Method\n                      , 3rd ed., John Wiley & Sons, New York, 2008.","DOI":"10.1002\/9780470277331"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/PL00007233"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"M. Basavaraju, L. S. Chandran, M. C. Golumbic, R. Mathew, and D. Rajendraprasad,\n                      Boxicity and separation dimension\n                      , in Proceedings of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2014), to appear; also available online from http:\/\/arXiv.org\/1404.4486.","DOI":"10.1007\/978-3-319-12340-0_7"},{"key":"atypb6","unstructured":"M. Basavaraju, L. S. Chandran, R. Mathew, and D. Rajendraprasad,\n                      Separation dimension of sparse graphs\n                      , in Proceedings of the 9th International Colloquium on Graph Theory and Combinatorics (ICGT 2014), to appear; http:\/\/arXiv.org\/abs\/1404.4484."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.06.005"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/120894099"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1950-0038922-4"},{"key":"atypb10","first-page":"609","volume":"10","author":"Erdo\u0308s P.","year":"1975","journal-title":"Infinite and Finite Sets"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(92)90023-Q"},{"key":"atypb12","first-page":"125","author":"Fu\u0308redi Z.","year":"2000","journal-title":"New York"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/BF00403406"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"atypb15","first-page":"219","volume":"73","author":"Kierstead H. A.","year":"1996","journal-title":"J. Combin. Theory Ser. A"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010405"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140973013","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:36:31Z","timestamp":1787319391000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140973013"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140973013"],"URL":"https:\/\/doi.org\/10.1137\/140973013","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}