Home | Issues | About JGAA | 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 Axis-Parallel Rectangles
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.
|
Journal Supporters
|