En teoría de grafos, un cactus (a veces llamado árbol de cactus) es un grafo conectado en el que dos ciclos simples tienen como máximo un vértice en común.De manera equivalente, es un grafo conectado en el que cada arista pertenece a un ciclo simple como máximo, o (para cactus no triviales) en el que cada bloque (subgrafo máximo sin vértices de corte) es una arista o un ciclo.[1] Un cactus triangular es un tipo especial de grafo cactus en el que cada ciclo tiene una longitud de tres y cada arista pertenece a un ciclo.[2] El cactus triangular más grande en cualquier grafo se puede encontrar en tiempo polinómico usando un algoritmo para el problema de la paridad de matroides.Dado que los grafos cactus triangulares son planos, el cactus triangular más grande se puede usar como una aproximación al subgrafo plano más grande, un subproblema importante en planarización.Como algoritmo de aproximación, este método tiene algoritmo de aproximación 4/9, el más conocido para el problema del subgrafo plano máximo.[3] El algoritmo para encontrar el cactus triangular más grande está asociado con un teorema de Lovász y Plummer que caracteriza el número de triángulos en este cactus más grande.Este resultado implica un análisis directo del algoritmo de aproximación 4/9 para el problema del subgrafo plano máximo sin usar la fórmula mín-máx anterior.Una conjetura importante relacionada con el cactus triangular es la conjetura de Rosa, llamada así por Alexander Rosa, que dice que todos los cactus triangulares son elegantes o casi elegantes.[6] Más precisamente En todos los cactus triangulares con t ≡ 0, los 1 mod 4 bloques son elegantes, y en aquellos con t ≡ 2, los 3 mod 4 bloques son casi elegantes.[7][8] Dado que los cactus son casos especiales de grafos planos exteriores, se pueden resolver varios problemas de optimización combinatoria en grafos en tiempo polinómico.[9] Los grafos cactus representan circuitos que tienen propiedades útiles.[13] Si un grafo cactus está conectado, y cada uno de sus vértices pertenece como máximo a dos bloques, entonces se llama cactus de Navidad.[15] Los grafos cactus se estudiaron por primera vez con el nombre de árboles de Husimi, término ideado por Frank Harary y George Eugene Uhlenbeck en honor al trabajo previo de Kôdi Husimi en estos grafos.Este uso tuvo poco que ver con el trabajo de Husimi, y ahora se usa el término más pertinente grafo bloque para esta familia.
