Files in this item

FilesDescriptionFormat

application/pdf

application/pdf9512323.pdf (4MB)Restricted to U of Illinois
(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


This item appears in the following Collection(s)

Item Statistics