Files in this item
Files  Description  Format 

application/pdf 9512323.pdf (4MB)  (no description provided) 
Description
Title:  Graph representations using stars, trees, intervals and boxes 
Author(s):  Chang, YiWu 
Doctoral Committee Chair(s):  Weischel, Paul W. 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
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 higherdimensional 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 kdimensional 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, YiWu 
Date Available in IDEALS:  20110507 
Identifier in Online Catalog:  AAI9512323 
OCLC Identifier:  (UMI)AAI9512323 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois 
Dissertations and Theses  Mathematics