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 and , of , where is the number of vertices in the given graph and is the number of vertex classes met by edge class . Recently, a tight extremal bound was proven which showed that given any plane graph , there always exist a cactus subgraph containing at least fraction of the triangular faces of . This result implies a direct analysis of the 4/9 - approximation algorithm for maximum planar subgraph problem without using the above min-max formula. 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 or nearly-graceful. 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 facility location problems which are NP-hard 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 graphs, a number of combinatorial optimization 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 been used in comparative genomics 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 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 has a greedy embedding in the Euclidean plane, an assignment of coordinates to the vertices for which greedy forwarding succeeds in routing messages between all pairs of vertices. In topological graph theory, the graphs whose cellular embeddings are all 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. History Cacti