Header menu link for other important links
X
Separation Dimension of Graphs and Hypergraphs
M. Basavaraju, L.S. Chandran, M.C. Golumbic, R. Mathew,
Published in Springer New York LLC
2016
Volume: 75
   
Issue: 1
Pages: 187 - 204
Abstract
Separation 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.
About the journal
JournalData powered by TypesetAlgorithmica
PublisherData powered by TypesetSpringer New York LLC
ISSN01784617