Abstract
The 2-level cactus introduced by Dinitz and Nutov in [5] is a data structure that represents the minimum and minimum+1 edgecuts of an undirected connected multi-graph G in a compact way. In this paper, we study planarity of the 2-level cactus, which can be used, e.g., in graph drawing. We give a new sufficient planarity criterion in terms of projection paths over a spanning subtree of a graph. Using this criterion, we show that the 2-level cactus of G is planar if the cardinality of a minimum edge-cut of G is not equal to 2, 3 or 5. On the other hand, we give examples for non-planar 2-level cacti of graphs with these connectivities.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. A. Benczúr. A representation of cuts within 6/5 times the edge connectivity with applications. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS’ 95), pages 92–103. IEEE Computer Society Press, 1995.
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.
Y. Dinitz. The 3-edge-components and a structural description of all 3-edge-cuts in a graph. In E. W. Mayr, editor, Graph Theoretic Cocepts in Computer Science, 18th International Workshop, (WG’ 92), volume 657 of Lecture Notes in Computer Science, pages 145–157. Springer, 1993.
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 (STOC’ 95), pages 509–518. ACM, The Association for Computing Machinery, 1995.
Y. Dinitz and Z. Nutov. A 2-level cactus tree model for the system of minimum and minimum+1 edge cuts of a graph and its incremental maintenance. Technical Report CS0915, Computer Science Department, Technion Haifa, 1997. 50 pages, available at http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgif1997/CS/CS0%915.
Y. Dinitz and J. Westbrook. Maintaining the classes of 4-edge-connectivity in a graph on-line. Algorithmica, 20:242–276, 1998.
Z. Galil and G. F. Italiano. Maintaining the 3-edge-connected components of a graph on-line. SIAM Journal on Computing, 22(1):11–28, 1993.
M. R. Henzinger and D. P. Williamson. On the number of small cuts in a graph. Information Processing Letters, 59(1):41–44, 1996.
C. Kuratowski. Sur le problème des courbes gauches en topologie. Fundamenta Mathematicae, 15:271–283, 1930.
S. MacLane. A combinatorial condition for planar graphs. Fundamenta Mathematicae, 28:22–32, 1937.
H. Nagamochi, K. Nishimura, and T. Ibaraki. Computing all small cuts in undirected networks. In D.-Z. Du, editor, Proceedings of the 5th International Symposium on Algorithms and Computing (ISAAC’ 94), volume 834 of Lecture Notes in Computer Science, pages 190–198. Springer, 1994.
C. Thomassen. Planarity and duality of finite and infinite graphs. Journal of Combinatorial Theory, Series B, 29:244–271, 1980.
V. V. Vazirani and M. Yannakakis. Suboptimal cuts: Their enumeration, weight and number. In W. Kuich, editor, Proceedings of the 19th International Colloquium on Automata, Languages and Programming, volume 623 of Lecture Notes in Computer Science, pages 366–377. Springer, 1992.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cornelsen, S., Dinitz, Y., Wagner, D. (2001). Planarity of the 2-Level Cactus Model. In: Brandstädt, A., Le, V.B. (eds) Graph-Theoretic Concepts in Computer Science. WG 2001. Lecture Notes in Computer Science, vol 2204. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45477-2_10
Download citation
DOI: https://doi.org/10.1007/3-540-45477-2_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42707-0
Online ISBN: 978-3-540-45477-9
eBook Packages: Springer Book Archive