# The ICICS/CS Reading Room

## UBC CS TR-89-24 Summary

- No on-line copy of this technical report is available.

- Bar-Representable Visibility Graphs and a Related Network Flow Problem, August 1989 Stephen Kenneth Wismath
A bar layout is a set of vertically oriented non-intersecting line segments in the plane
called bars. The visibility graph associated with a layout is defined as the graph whose
vertices correspond to the bars and whose edges represent the horizontal visibilities between
pairs of bars.
\n This dissertation is concerned with the characterization of bar-representable graphs:
those graphs which are the visibility graphs of some bar layout. A polynomial time algorithm for determining if a given graph is bar-representable, and the subsequent construction
of an associated layout are provided. Weighted and directed versions of the problem are
also formulated and solved; in particular, polynomial time algorithms for the layout of such
graphs are developed.
\n The Planar Full Flow problem is to determine a plane embedding and an (acyclic)
orientation of an undirected planar network that admits a feasible flow, that uses all arcs
(except those incident upon the source or sink) to full capacity and maintains planarity.
The connection of this flow problem to bar-representable graphs is exploited to solve the
weighted case of the latter. As evidence that both the acyclicity and planarity constraints
are necessary to obtain a polynomial algorithm for this problem, two natural variants of
the Full Flow problem are shown to be strongly NP-Complete.

If you have any questions or comments regarding this page please send mail to
help@cs.ubc.ca.