Characterizing Families of Cuts That Can Be Represented by Axis-Parallel Rectangles

Brandes, Ulrik and Cornelsen, Sabine and Wagner, Dorothea (2004) Characterizing Families of Cuts That Can Be Represented by Axis-Parallel Rectangles. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003 , pp. 357-368(Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_33).

Full text not available from this repository.

Abstract

A 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 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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-24595-7_33
Classifications: Z Theory > Z.250 Geometry
URI: http://gdea.informatik.uni-koeln.de/id/eprint/465

Actions (login required)

View Item View Item