Problem of the Week
Hilton Memorial Lecture
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.