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, Perugia, Italy , 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
ID Code:465

Repository Staff Only: item control page

References

U. Brandes, S. Cornelsen, and D. Wagner. How to draw the minimum cuts of a planar graph. In J. Marks, editor, Proceedings of the 8th International Symposium on Graph DRawing (GD 2000), volume 1984 of Lecture Notes in Computer Science, pages 103-114. Springer, 2001.

S. Cornelsen and D. Wagner. Completely connected clustered graphs. To appear in Proceedings of the 29th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2003).

G. Di Battista, W. Didimo, and A. Marcandalli. Planarization of clustered graphs. In M. Jünger and P. Mutzel, editors, Proceedings of the 9th International Symposium on Graph Drawing (GD2001), volume 2265 of Lecture Notes in Computer Science, pages 60-74. Springer, 2002.

Y. Dinitz, A. V. Karzanov, and M. Lomonosov. On the structure of a family of minimal weighted cuts in a graph. In A. Fridman, editor, Studies in Discrete Optimization, pages 290-306. Nauka, 1976. (in Russian).

Y. Dinitz and Z. Nutov. A 2-level cactus model for the system of minimum and minimum+1 edge-cuts in a graph and its incremental maintenance. In Proceedings of the 27th Annual ACM Symposium on the Theory of Computing Machinery, 1995.

Q. Feng, R. F. Cohen, and P. Eades. Planarity for clustered graphs. In P. Spirakis, editor, Proceedings of the 3rd European Symposium on Algorithms (ESA '95), volume 979 of Lecture Notes in Computer Science, pages 213-226. Springer, 1995.

U. Fößmeier and M. Kaufmann. Drawing high degree graphs with low bend numbers. In F. J. Brandenburg, editor, Proceedings of the 3rd International Symposium on Graph Drawing (GD '95), volume 1027 of Lecture Notes in Computer Science, pages 254-266. Springer, 1996.

G. W. Klau and P. Mutzel. Quasi orthogonal drawing of planar graphs. Technical Report MPI-I-98-1-013, Max-Planck-Institut für Informatik, Saarbrücken, Germany, 1998. Available at http://data.mpi-sb.mpg.de/internet/reports.nsf.

D. Lütke-Hüttmann. Knickminimales Zeichen 4-planarer Clustergraphen. Master's thesis, Universität des Saarlandes, 1999. (Diplomarbeit).

R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM Journal on Computing, 16:421-444, 1987.

R. Tamassia, G. Di Battista, and C. Batini. Automatic graph drawing and readability of diagrams. IEEE Transactions on Systems, Man and Cybernetics, 18(1):61-79, 1988.