====== Alice Dean (Skidmore) ======

====== Characterizations of Unit-Bar Visibility Graphs ======

===== Abstract for the Combinatorics Seminar =====

===== Abstract for the Combinatorics and Algebra Seminars 2005 May 10 =====

Representations of graphs using horizontal bars for vertices and vertical visibilities for edges have been studied since the mid 1980s, motivated by applications to circuit design and display of data. Graphs that can be represented in this way have been fully characterized, but the bar lengths may differ by impractical amounts. I consider graphs that can be represented using bars all of equal length. These graphs, called //unit-bar visibility graphs// (or //UBVGs//), have not been fully characterized. I will discuss results for several classes of graphs, including trees and outerplanar graphs. The final result is a characterization of the //triangulated polygons// (//TPs//) that are UBVGs. The characterization uses a character string associated with each TP to determine if a UBV layout exists and if so, to produce such a layout.

This is joint work with E. Gethner and J. Hutchinson and, separately, with N. Veytsel.