View source for Cactus graph

{{short description|Mathematical tree of cycles}}
[[Image:Cactus graph.svg|thumb|225px|A cactus graph]]

In [[graph theory]], a '''cactus''' (sometimes called a '''cactus tree''') is a [[connected graph]] in which any two simple [[cycle (graph theory)|cycle]]s have at most one [[Vertex (graph theory)|vertex]] in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or (for nontrivial cacti) in which every block (maximal subgraph without a [[cut-vertex]]) is an edge or a cycle.

==Properties==
Cacti are [[outerplanar graph]]s. Every [[pseudoforest|pseudotree]] is a cactus.  A nontrivial graph is a cactus if and only if every [[Glossary of graph theory#block|block]] is either a [[cycle (graph theory)|simple cycle]] or a single edge.

The family of graphs in which each [[component (graph theory)|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''<sub>4</sub>.<ref>{{citation |last1=El-Mallah |first1=Ehab |last2=Colbourn |first2=Charles J. |author2-link=Charles Colbourn |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}}</ref>

==Triangular cactus==
[[File:Friendship graphs.svg|thumb|upright=1.6|[[Friendship graph]]s are triangular cacti]]
A triangular cactus is a special type of cactus graph such that each cycle has length three and each edge belongs to a cycle. For instance, the [[friendship graph]]s, graphs formed from a collection of triangles joined together at a single shared vertex, are triangular cacti. As well as being cactus graphs the triangular cacti are also [[block graph]]s and [[locally linear graph]]s.

Triangular cactuses have the property that they remain connected if any [[matching (graph theory)|matching]] is removed from them; for a given number of vertices, they have the fewest possible edges with this property. Every tree with an odd number of vertices may be augmented to a triangular cactus by adding edges to it, 
giving a minimal augmentation with the property of remaining connected after the removal of a matching.<ref>{{citation
 | last1 = Farley | first1 = Arthur M.
 | last2 = Proskurowski | first2 = Andrzej
 | doi = 10.1002/net.3230120404
 | issue = 4
 | journal = Networks
 | mr = 686540
 | pages = 393–403
 | title = Networks immune to isolated line failures
 | volume = 12
 | year = 1982}}</ref>

The largest triangular cactus in any graph may be found in [[polynomial time]] using an algorithm for the [[matroid parity problem]]. Since triangular cactus graphs are [[planar graph]]s, the largest triangular cactus can be used as an approximation to the largest planar subgraph, an important subproblem in [[planarization]]. As an [[approximation algorithm]], this method has [[approximation ratio]] 4/9, the best known for the maximum planar subgraph problem.<ref>{{citation
 | last1 = Călinescu | first1 = Gruia
 | last2 = Fernandes | first2 = Cristina G
 | last3 = Finkler | first3 = Ulrich
 | last4 = Karloff | first4 = Howard
 | doi = 10.1006/jagm.1997.0920
 | journal = Journal of Algorithms
 | pages = 269–302
 | series = 2
 | title = A Better Approximation Algorithm for Finding Planar Subgraphs
 | volume = 27
 | issue = 2
 | year = 2002| citeseerx = 10.1.1.47.4731
 | s2cid = 8329680
 }}</ref>

The algorithm for finding the largest triangular cactus is associated with a theorem of Lovász and Plummer that characterizes the number of triangles in this largest cactus.<ref>{{Citation|last1=Lovász|first1=L.|author1-link=László Lovász|last2= Plummer |first2=M.D.|author-link2=Michael D. Plummer|date=2009|title=Matching Theory|publisher=AMS Chelsea Publishing Series|isbn= 9780821847596}}</ref>
Lovász and Plummer consider pairs of partitions of the vertices and edges of the given graph into subsets, with the property that every triangle of the graph either has two vertices in a single class of the vertex partition or all three edges in a single class of the edge partition; they call a pair of partitions with this property ''valid''.
Then the number of triangles in the largest triangular cactus equals the maximum, over pairs of valid partitions <math>\mathcal{P}=\{V_1, V_2, \dots, V_k\}</math> and <math>\mathcal{Q} = \{E_1, E_2, \dots, E_m\}</math>, of
:<math>\sum_{i=1}^{m}\frac{(u_i - 1)}{2} + n - k,</math>,
where <math>n</math> is the number of vertices in the given graph and <math>u_i</math> is the number of vertex classes met by edge class <math>E_i</math>.

Every [[plane graph]] <math>G</math> contains a cactus subgraph <math>C \subseteq G</math> which includes at least <math>1/6</math> fraction of the triangular faces of <math>G</math>. This result implies a direct analysis of the 4/9 - approximation algorithm for maximum planar subgraph problem without using the above min-max formula.<ref>{{citation
 | last1 = Chalermsook | first1 = Parinya
 | last2 = Schmid | first2 = Andreas
 | last3 = Uniyal | first3 = Sumedha
 | editor1-last = Niedermeier | editor1-first = Rolf
 | editor2-last = Paul | editor2-first = Christophe
 | arxiv = 1804.03485
 | contribution = A tight extremal bound on the Lovász cactus number in planar graphs
 | doi = 10.4230/LIPIcs.STACS.2019.19
 | pages = 19:1–19:14
 | publisher = Schloss Dagstuhl - Leibniz-Zentrum für Informatik
 | series = LIPIcs
 | title = 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany
 | volume = 126
 | year = 2019| doi-access = free
 | isbn = 9783959771009
 | s2cid = 4751972
 }}</ref>

===Rosa's Conjecture===

An important conjecture related to the triangular cactus is the '''Rosa's Conjecture''', named after '''Alexander Rosa''', which says that all triangular cacti are [[Graceful_labeling | graceful]] or nearly-graceful.<ref name="Rosa1988">{{citation|last=Rosa|first=A.|title=Cyclic Steiner Triple Systems and Labelings of Triangular Cacti|journal=Scientia|volume=1|pages=87–95|year=1988}}.</ref> More precisely 

''All triangular cacti with t ≡ 0, 1 mod 4 blocks are graceful, and those with t ≡ 2, 3 mod 4 are near graceful.''

==Algorithms and applications==
Some [[Optimal facility location|facility location problem]]s which are [[NP-hard]] for general graphs, as well as some other graph problems,  may be solved in [[polynomial time]] for cacti.<ref>{{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  |publisher=Springer-Verlag |series=[[Lecture Notes in Computer Science]] |volume=3827 |pages=693–703 |title=Algorithms and Computation, 16th Int. Symp., ISAAC 2005| doi=10.1007/11602613_70|isbn=978-3-540-30935-2 }}</ref><ref>{{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) |isbn=978-0-7695-2397-2|s2cid=15963409 }}</ref>

Since cacti are special cases of [[outerplanar graph]]s, a number of [[combinatorial optimization]] problems on graphs  may be solved for them in [[polynomial time]].<ref>{{Citation |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 |postscript=.|doi-access=free }} Translated from ''Notices of the BSSR Academy of Sciences, Ser. Phys.-Math. Sci.'', (1984) no. 3, pp. 109-111 {{in lang|ru}}</ref>

Cacti represent [[electrical circuit]]s that have useful properties. An early application of cacti was associated with the representation of op-amps.<ref>{{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=33 |issue=4 |pages=398–405 |year=1986 |doi=10.1109/TCS.1986.1085935}}</ref><ref>{{citation |first1=Tetsuo |last1=Nishi |first2=Leon O. |last2=Chua |author2-link=Leon O. Chua |title=Uniqueness of solution for nonlinear resistive circuits containing CCCS's or VCVS's whose controlling coefficients are finite |journal=IEEE Transactions on Circuits and Systems |volume=33 |issue=4 |pages=381–397 |year=1986 |doi=10.1109/TCS.1986.1085934}}</ref><ref>{{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=766–769 |year=1991}}</ref>

Cacti have also been used in [[comparative genomics]] as a way of representing the relationship between different genomes or parts of genomes.<ref>{{citation |first1=Benedict |last1=Paten |first2=Mark |last2=Diekhans |first3=Dent |last3=Earl |first4=John |last4=St. John |first5=Jian |last5=Ma |first6=Bernard |last6=Suh |first7=David |last7=Haussler |title=Research in Computational Molecular Biology |volume=6044 |pages=[https://archive.org/details/researchincomput0000reco/page/410 410–425] |year=2010 |doi=10.1007/978-3-642-12683-3_27 |chapter=Cactus Graphs for Genome Comparisons |series=Lecture Notes in Computer Science |isbn=978-3-642-12682-6 |chapter-url-access=registration |chapter-url=https://archive.org/details/researchincomput0000reco/page/410 }}</ref>

If a cactus is connected, and each of its vertices belongs to at most two blocks, then it is called a '''Christmas cactus'''. Every [[polyhedral graph]] has a Christmas cactus subgraph that includes all of its vertices, a fact that plays an essential role in a proof by {{harvtxt|Leighton|Moitra|2010}} that every polyhedral graph has a [[greedy embedding]] in the [[Euclidean plane]], an assignment of coordinates to the vertices for which [[Geographic routing|greedy forwarding]] succeeds in routing messages between all pairs of vertices.<ref>{{citation
 | last1 = Leighton | first1 = Tom |author-link1= F. Thomson Leighton
 | last2 = Moitra | first2 = Ankur
 | issue = 3
 | journal = [[Discrete & Computational Geometry]]
 | pages = 686–705
 | title = Some Results on Greedy Embeddings in Metric Spaces
 | volume = 44
 | doi = 10.1007/s00454-009-9227-6
 | url = http://people.csail.mit.edu/moitra/docs/dcg-greedy.pdf
 | year = 2010| s2cid = 11186402 | doi-access = free
 }}.</ref>

In [[topological graph theory]], the graphs whose [[graph embedding|cellular embeddings]] are all [[planar graph|planar]] are exactly the subfamily of the cactus graphs with the additional property that each vertex belongs to at most one cycle. These graphs have two forbidden minors, the diamond graph and the five-vertex [[friendship graph]].<ref>{{citation
 | last1 = Nordhaus | first1 = E. A.
 | last2 = Ringeisen | first2 = R. D.
 | last3 = Stewart | first3 = B. M.
 | last4 = White | first4 = A. T.
 | doi = 10.1016/0095-8956(72)90040-8
 | journal = Journal of Combinatorial Theory
 | mr = 0299523
 | pages = 260–267
 | series = Series B
 | title = A Kuratowski-type theorem for the maximum genus of a graph
 | volume = 12
 | issue = 3
 | year = 1972| doi-access = 
 }}</ref>

==History==

Cacti 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 [[Kôdi Husimi]].<ref>{{citation |last1=Harary |first1=Frank |last2=Uhlenbeck |author-link1 = Frank Harary |first2=George E. |author-link2=George Eugene Uhlenbeck |title=On the number of Husimi trees, I |journal=[[Proceedings of the National Academy of Sciences]] |volume=39 |year=1953 |pages=315–322 |mr=0053893 |doi=10.1073/pnas.39.4.315 |issue=4|pmid=16589268 |pmc=1063779|bibcode=1953PNAS...39..315H |doi-access=free }}</ref><ref>{{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 |mr=0038903 |doi=10.1063/1.1747725 |issue=5|bibcode=1950JChPh..18..682H }}</ref> The same Harary–Uhlenbeck paper reserves the name "cactus" for graphs of this type in which every cycle is a triangle, but now allowing cycles of all lengths is standard.

Meanwhile, the name '''Husimi tree''' commonly came to refer to graphs in which every [[Glossary of graph theory|block]] is a [[complete graph]] (equivalently, the intersection graphs of the blocks in some other graph).  This usage had little to do with the work of Husimi, and the more pertinent term [[block graph]] is now used for this family; however, because of this ambiguity this phrase has become less frequently used to refer to cactus graphs.<ref>See, e.g., {{MR|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 [[Mehdi Behzad]] and [[Gary Chartrand]].</ref>

==References==
{{reflist|colwidth=30em}}

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

[[Category:Graph families]]
[[Category:Planar graphs]]
[[Category:Integrated circuits]]