Planaridad agrupada
En el dibujo de gráficos , un gráfico plano agrupado es un gráfico junto con una agrupación jerárquica en sus vértices, de modo que el gráfico se dibuja junto con una colección de curvas cerradas simples que rodean cada grupo, de modo que no hay cruces entre los bordes del gráfico o los grupos. [1]
El agrupamiento se puede describir combinatoriamente mediante una colección de subconjuntos de vértices de modo que, para cada dos subconjuntos, ambos son disjuntos o uno está contenido en el otro. No se requiere que la agrupación sea máxima ni que todos los vértices pertenezcan a una agrupación. En un dibujo plano agrupado, dos bordes no pueden cruzarse entre sí (es decir, el gráfico debe ser plano ), dos de las curvas que representan grupos no pueden cruzarse entre sí, un borde puede cruzar un límite de grupo solo si conecta un vértice interior el grupo a un vértice fuera del grupo, y cuando un borde y un límite de grupo se cruzan, pueden cruzarse solo una vez. [1] Después de mucho trabajo anterior sobre el problema, Radoslav Fulek y Csaba Tóth encontraron en 2019 un algoritmo de tiempo polinomial que prueba la planaridad agrupada. [2]
