A study of unit bar-visibility graphs
by Wiglesworth, Lesley Wellington, Ph.D., UNIVERSITY OF LOUISVILLE, 2008, 92 pages; 3308338

Abstract:

Bar-visibility graphs were introduced in the 1970s as a method to test printed circuit boards. Wismath and independently Tomassia and Tollis provided characterizations in the mid-1980s. Unit bar-visibility graphs are a type of bar-visibility graph in which all bars have the same unit length. This length restriction was motivated by circuits in which all components have near the same length.

This dissertation provides general results of unit bar-visibility graphs and then focuses on unit bar-visibility graphs having unit bar layouts with width less than two. Two characterizations of these graphs are provided. One characterization provides information on the unit bar layout of such a graph, and the other is tailored to finding a polynomial time algorithms to determine whether a graph has such a unit bar layout. Finally, Chapter 5 addresses induced subgraphs of grids, a challenging subclass of graphs that will guide the design of a general polynomial time algorithm for recognition of these graphs.

 
Advisor
SchoolUNIVERSITY OF LOUISVILLE
SourceDAI/B 69-03, p. , Jun 2008
Source TypeDissertation
SubjectsMathematics; Computer science
Publication Number3308338
Adobe PDF Access the complete dissertation:
 

» Find an electronic copy at your library.
  Use the link below to access a full citation record of this graduate work:
  http://gateway.proquest.com/openurl%3furl_ver=Z39.88-2004%26res_dat=xri:pqdiss%26rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation%26rft_dat=xri:pqdiss:3308338
  If your library subscribes to the ProQuest Dissertations & Theses (PQDT) database, you may be entitled to a free electronic version of this graduate work. If not, you will have the option to purchase one, and access a 24 page preview for free (if available).

About ProQuest Dissertations & Theses
With over 2.3 million records, the ProQuest Dissertations & Theses (PQDT) database is the most comprehensive collection of dissertations and theses in the world. It is the database of record for graduate research.

The database includes citations of graduate works ranging from the first U.S. dissertation, accepted in 1861, to those accepted as recently as last semester. Of the 2.3 million graduate works included in the database, ProQuest offers more than 1.9 million in full text formats. Of those, over 860,000 are available in PDF format. More than 60,000 dissertations and theses are added to the database each year.

If you have questions, please feel free to visit the ProQuest Web site - http://www.proquest.com - or call ProQuest Hotline Customer Support at 1-800-521-3042.