Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Boxicity and Separation Dimension
verfasst von : Manu Basavaraju, L. Sunil Chandran, Martin Charles Golumbic, Rogers Mathew, Deepak Rajendraprasad
Erschienen in: Graph-Theoretic Concepts in Computer Science
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
A family \(\mathcal {F}\) of permutations of the vertices of a hypergraph \(H\) is called pairwise suitable for \(H\) if, for every pair of disjoint edges in \(H\), there exists a permutation in \(\mathcal {F}\) in which all the vertices in one edge precede those in the other. The cardinality of a smallest such family of permutations for \(H\) is called the separation dimension of \(H\) and is denoted by \(\pi (H)\). Equivalently, \(\pi (H)\) is the smallest natural number \(k\) so that the vertices of \(H\) can be embedded in \(\mathbb {R}^k\) 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.