Cactus graph
Encyclopedia
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a cactus (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 belongs to at most one simple cycle. Equivalently, every block (maximal subgraph without a cut-vertex) is an edge or a cycle.
Properties
Cacti are outerplanar graphOuterplanar graph
In graph theory, an undirected graph is an outerplanar graph if it can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing. That is, no vertex is totally surrounded by edges...
s. Every pseudotree
Pseudoforest
In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be...
is a cactus. A graph is a cactus if and only if every block
Glossary of graph theory
Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with current usage....
is either a simple cycle or a single edge.
The family of graphs in which each 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
Diamond graph
In the mathematical field of graph theory, the diamond graph is a planar undirected graph with 4 vertices and 5 edges. It consists of a complete graph K_4 minus one edge....
formed by removing an edge from the complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
K4.
Algorithms and applications
Some facility location problems which are NP-hardNP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
for general graphs, as well as some other graph problems, may be solved in polynomial time for cacti.
Since cacti are special cases of outerplanar graph
Outerplanar graph
In graph theory, an undirected graph is an outerplanar graph if it can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing. That is, no vertex is totally surrounded by edges...
s, a number of combinatorial optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
problems on graphs may be solved for them in polynomial time.
Cacti represent electrical circuits that have useful properties. An early application of cacti was associated with the representation of op-amps.
Cacti have also recently been used in comparative genomics
Comparative genomics
Comparative genomics is the study of the relationship of genome structure and function across different biological species or strains. Comparative genomics is an attempt to take advantage of the information provided by the signatures of selection to understand the function and evolutionary...
as a way of representing the relationship between different genomes or parts of genomes.
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
Polyhedral graph
In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs...
has a Christmas cactus subgraph that includes all of its vertices, a fact that plays an essential role in a proof by that every polyhedral graph may be embedded in the plane in such a way that greedy forwarding
Geographic routing
Geographic routing is a routing principle that relies on geographic position information. It is mainly proposed for wireless networks and based on the idea that the source sends a message to the geographic location of the destination instead of using the network address...
succeeds in routing messages between all pairs of vertices.
History
Cacti were first studied under the name of Husimi trees, bestowed on them by Frank HararyFrank Harary
Frank Harary was a prolific American mathematician, who specialized in graph theory. He was widely recognized as one of the "fathers" of modern graph theory....
and George Eugene Uhlenbeck
George Eugene Uhlenbeck
George Eugene Uhlenbeck was a Dutch-American theoretical physicist.-Background and education:George Uhlenbeck was the son of Eugenius and Anne Beeger Uhlenbeck...
in honor of previous work on these graphs by Kodi Husimi. 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 more commonly came to refer to graphs in which every block
Glossary of graph theory
Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with current usage....
is a complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
(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
Block graph
In graph theory, a branch of combinatorial mathematics, a block graph is a type of undirected graph in which every biconnected component is a clique...
is now used for this family.