Home  Issues  Aims and Scope  Instructions for Authors 
Special Issue on Selected Papers from the Eleventh International Symposium on Graph Drawing, GD 2003
DOI: 10.7155/jgaa.00101
Characterizing Families of Cuts that can be Represented by AxisParallel Rectangles
Vol. 9, no. 1, pp. 99115, 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 axisparallel 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 axisparallel rectangles if it exists.
