Separation Dimension of Graphs and Hypergraphs

Simple item page
dc.contributor.authorBasavaraju, M.
dc.contributor.authorSunil Chandran, L.S.
dc.contributor.authorGolumbic, M.C.
dc.contributor.authorMathew, R.
dc.contributor.authorRajendraprasad, D.
dc.date.accessioned2026-02-05T09:33:13Z
dc.date.issued2016
dc.description.abstractSeparation dimension of a hypergraph H, denoted by ?( H) , is the smallest natural number k so that the vertices of H can be embedded in Rk such that any two disjoint edges of H can be separated by a hyperplane normal to one of the axes. We show that the separation dimension of a hypergraph H is equal to the boxicity of the line graph of H. This connection helps us in borrowing results and techniques from the extensive literature on boxicity to study the concept of separation dimension. In this paper, we study the separation dimension of hypergraphs and graphs. © 2015, Springer Science+Business Media New York.
dc.identifier.citationAlgorithmica, 2016, 75, 1, pp. 187-204
dc.identifier.issn1784617
dc.identifier.urihttps://doi.org/10.1007/s00453-015-0050-6
dc.identifier.urihttps://idr.nitk.ac.in/handle/123456789/26014
dc.publisherSpringer New York LLC barbara.b.bertram@gsk.com
dc.subjectSeparation
dc.subjectBoxicity
dc.subjectChromatic number
dc.subjectDisjoint edges
dc.subjectGraphs and hypergraphs
dc.subjectHypergraph
dc.subjectLine graph
dc.subjectNatural number
dc.subjectScrambling permutation
dc.subjectGraph theory
dc.titleSeparation Dimension of Graphs and Hypergraphs

Files

Collections

Journal Articles