## Files in this item

FilesDescriptionFormat

application/pdf

9512323.pdf (4MB)
(no description provided)PDF

## Description

 Title: Graph representations using stars, trees, intervals and boxes Author(s): Chang, Yi-Wu Doctoral Committee Chair(s): Weischel, Paul W. Department / Program: Mathematics Discipline: Mathematics Degree Granting Institution: University of Illinois at Urbana-Champaign Degree: Ph.D. Genre: Dissertation Subject(s): Mathematics Abstract: 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. Issue Date: 1994 Type: Text Language: English URI: http://hdl.handle.net/2142/21303 Rights Information: Copyright 1994 Chang, Yi-Wu Date Available in IDEALS: 2011-05-07 Identifier in Online Catalog: AAI9512323 OCLC Identifier: (UMI)AAI9512323
﻿