Characterizing Families of Cuts That Can Be Represented by AxisParallel RectanglesBrandes, Ulrik and Cornelsen, Sabine and Wagner, Dorothea (2004) Characterizing Families of Cuts That Can Be Represented by AxisParallel Rectangles. In: Graph Drawing 11th International Symposium, GD 2003, September 2124, 2003 , pp. 357368(Official URL: http://dx.doi.org/10.1007/9783540245957_33). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783540245957_33
AbstractA drawing of a family of cuts of a graph is an augmented drawing of the graph such that every cut 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.
Actions (login required)
