Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00101 Characterizing Families of Cuts that can be Represented by Axis-Parallel Rectangles Ulrik Brandes , Sabine Cornelsen , and Dorothea Wagner Vol. 9, no. 1, pp. 99-115, 2005. Regular paper Abstract A drawing of a family of cuts of a graph is an augmented drawing of the graph such that every cut in the family is represented by a simple closed curve and vice versa. We show that the families of cuts that admit a drawing in which every cut is represented by an axis-parallel rectangle are exactly those that have a cactus model that can be rooted such that edges of the graph that cross a cycle of the cactus point to the root. This includes the family of all minimum cuts of a graph. The proof also yields an efficient algorithm to construct a drawing with axis-parallel rectangles if it exists.
|
Submitted: January 2004. Revised: July 2005. Communicated by Giuseppe Liotta |
Journal of Graph Algorithms and Applications |