Cactus graph

A cactus graph (sometimes called a cactus tree) is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, every edge in such a graph may belong to at most one cycle.

Cactus graphs were first studied under the name of Husimi trees, bestowed on them by Frank Harary and George Eugene Uhlenbeck in honor of previous work on these graphs by Kodi Husimi. [citation|last1=Harary|first1=F.|last2=Uhlenbeck|first2=G.|title=On the number of Husimi trees, I|journal=Proceedings of the National Academy of Sciences|volume=39|year=1953|pages=315–322|id=MathSciNet|id=0053893|doi=10.1073/pnas.39.4.315.] [citation|last=Husimi|first=Kodi|title=Note on Mayers' theory of cluster integrals|journal=Journal of Chemical Physics|volume=18|year=1950|pages=682–684|id=MathSciNet|id=0038903|doi=10.1063/1.1747725.] The same Harary–Uhlenbeck paper reserves the name "cactus" for graphs of this type in which every cycle is a triangle. However, the Husimi tree name also came to refer to graphs in which every biconnected component is a complete graph, and (perhaps due to this confusion) fell into disuse, while the name "cactus" came to mean the more general class of graph. [See, e.g., MathSciNet|0659742, a 1983 review by Robert E. Jamison of a paper using the other definition, which attributes the ambiguity to an error in a book by Behzad and Chartrand.]

Properties

Cactus graphs are outerplanar graphs. Every pseudotree is a cactus graph. A graph is a cactus graph if and only if every biconnected component is either a simple cycle or a single edge.

The family of graphs in which each connected component is a cactus is downwardly closed under graph minor operations. This graph family may be characterized by a single forbidden minor, the four-vertex "diamond graph" formed by removing an edge from the complete graph "K"₄. [citation|last1=El-Mallah|first1=Ehab|last2=Colbourn|first2=Charles L.|title=The complexity of some edge deletion problems|journal=IEEE Transactions on Circuits and Systems|volume=35|issue=3|year=1988|pages=354–362|doi=10.1109/31.1748.]

Algorithms and applications

Some facility location problems which are NP-hard for general graphs, as well as some other graph problems, may be solved in polynomial time for cactus graphs. [citation|first1=Boaz|last1=Ben-Moshe|first2=Binay|last2=Bhattacharya|first3=Qiaosheng|last3=Shi|year=2005|contribution=Efficient algorithms for the weighted 2-center problem in a cactus graph|contribution-url=http://www.cs.sfu.ca/~qshi1/personal/papers/isaac2005.pdf|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=3827|pages=693–703|title=Algorithms and Computation, 16th Int. Symp., ISAAC 2005.] [citation|first1=Blaz|last1=Zmazek|first2=Janez|last2=Zerovnik|year=2005|pages=536–541|doi=10.1109/IV.2005.48|contribution=Estimating the traffic on weighted cactus networks in linear time|title=Ninth International Conference on Information Visualisation (IV'05)|pages=536–541.]

Since cactus graphs are outerplanar, a number of combinatorial optimization problems on graphs may be solved for them in polynomial time, [cite journal|author=Korneyenko, N. M.|title=Combinatorial algorithms on a class of graphs|journal=Discrete Applied Mathematics|volume=54|issue=2–3|pages=215–217|year=1994|doi=10.1016/0166-218X(94)90022-1 Translated from "Notices of the BSSR Academy of Sciences, Ser. Phys.-Math. Sci.", (1984) no. 3, pp. 109-111 ru icon] see "Series-parallel graph#Generalization" for details.

Cactus graphs represent electrical circuits that provably have useful properties. An early application of the cactus graphs was associated with the representation of op-amps by means of cactus graphs. [citation|first1=Tetsuo|last1=Nishi|first2=Leon O.|last2=Chua|author2-link=Leon O. Chua|title=Topological proof of the Nielsen-Willson theorem|journal=IEEE Transactions on Circuits and Systems|volume=CAS-33|issue=4|pages=398–405|year=1986.] [citation|first1=Tetsuo|last1=Nishi|first2=Leon O.|last2=Chua|author2-link=Leon O. Chua|title=Uniqueness of solution for nonlinear resisitive circuits containing CCCS’s or VCVS’s whose controlling coefficients are finite|journal=IEEE Transactions on Circuits and Systems|volume=CAS-33|issue=4|pages=381–397|year=1986.] [citation|first=Tetsuo|last=Nishi|contribution=On the number of solutions of a class of nonlinear resistive circuit|title=Proceedings of the IEEE International Symposium on Circuits and Systems, Singapore|pages=pages 766–769|year=1991.]

References

External links

* [http://www.angelfire.com/electronic2/cas/ Application of Cactus Graphs in Analysis and Design of Electronic Circuits]