2026-09-21T08:09:58Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/21303 2023-07-10 col_2142_5131 col_2142_16340 com_2142_5130 com_2142_16339 com_2142_8903

Weischel, Paul W. Chang, Yi-Wu 2011-05-07T13:04:42Z 2011-05-07T13:04:42Z 10000-01-01 1994 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. Made available in DSpace on 2011-05-07T13:04:42Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9512323.pdf: 3860089 bytes, checksum: 237a2ede4d7f0eb994e49dc3e8992142 (MD5) Previous issue date: 1994 Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:49:51Z Item is restricted indefinitely. Restriction data tranferred 2014-07-01T11:22:43-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission ETDs are only available to UIUC Users without author permission U of I Only AAI9512323 (UMI)AAI9512323 http://hdl.handle.net/2142/21303 eng Copyright 1994 Chang, Yi-Wu Mathematics Graph representations using stars, trees, intervals and boxes text Mathematics Mathematics University of Illinois at Urbana-Champaign Dissertation Ph.D.