Graph representations using stars, trees, intervals and boxes

We introduce star number (tree number) of a graph G, which is the minimum t such that G is the intersection graph of unions of t substars (subtrees) of a host tree. We characterize the graphs with star number 1 and prove that a planar graph has star number at most 3. We study bounds on these two parameters and compare them with interval number. We prove that the star number is at most $\lceil(n + 1)/4\rceil,$ where n is the number of vertices. We also show the independence of interval number and star number.We also prove some results about representations using intervals and higher-dimensional objects. The rectangle number of G is the minimum t such that G has an intersection representation in which each vertex is assigned a union of t boxes in the plane. The rectangle number of a multipartite graph is at most 2. The rectangle number of a k-dimensional cube is at most $\lceil k/4\rceil,$ except for k = 4. For an intersection representation of a digraph, we assign a source set $S\sb u$ and a sink set $T\sb u$ to each vertex u such that uv is an edge if and only if $S\sb u\cap T\sb v\ne\emptyset.$ The interval number of a digraph is the minimum t such that D has an intersection representation in which each source set and sink set is a union of t intervals. We prove that the interval number of a digraph is at most n/(lgn + 1). The bar visibility number of a graph G is the minimum t such that G has an representation in which each vertex is assigned a union of t horizontal intervals (bars) in the plane such that two vertices u,v are adjacent if and only if some bar for u can see some bar for v by an unblocked vertical line. We prove that the bar visibility number is at most $\lceil n/6\rceil + 2$ for graphs with n vertices.U of I OnlyETDs are only available to UIUC Users without author permissio