Department of
Applied
Mathematics

Separation Dimension of Graphs and Hyper Graphs

Sunil Chandran

Indian Institute of Science, Bangalore

Abstract

The separation dimension of a hyper graph G is the smallest natural number k for which the vertices of G can be embedded in 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 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. It can be shown that the separation dimension of a hyper graph G equals the boxicity of the line graph of G, where boxicity of a graph H is defined as the smallest integer d such that H can be represented as the intersection graph of d-dimensional axis parallel boxes. In this talk we discuss the relation of separation dimension with various other graph theoretic parameters. We will also mention some of the recently introduced variants of separation dimension: Induced separation dimension (from the team of Martin Golumbic) and fractional separation dimension (D. B. West and S. Loeb) and discuss the improvements of certain results on separation dimension by Scott and Wood.