logo móvil
Contáctanos

Graficar planaridad reemplazando cliques con caminos

Autores: Angelini, Patrizio; Eades, Peter; Hong, Seok-Hee; Klein, Karsten; Kobourov, Stephen; Liotta, Giuseppe; Navarra, Alfredo; Tappini, Alessandra

Idioma: Inglés

Editor: MDPI

Año: 2020

Descargar PDF

Acceso abierto

Artículo científico
2020

Graficar planaridad reemplazando cliques con caminos


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería de Software

Palabras clave

Introduce
Estudios
Problema más allá de la planaridad
-2
Subgrafo planar
Complejidad
NP-completo
Grafo 3-planar
Tiempo lineal
Grafo 1-planar
Planaridad híbrida
Dibujo de gráficos más allá de la planaridad

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 37

Citaciones: Sin citaciones


Descripción
Este documento presenta y estudia el siguiente problema más allá de la planaridad, al que llamamos -2. Sea un grafo topológico simple cuyos vértices están divididos en subconjuntos de tamaño a lo sumo , cada uno induciendo una clique. -2 pregunta si es posible obtener un subgrafo planar de al eliminar aristas de cada clique para que el subgrafo inducido por cada subconjunto sea un camino. Investigamos la complejidad de este problema en relación con la -planaridad. En particular, demostramos que -2 es NP-completo incluso cuando y es un grafo 3-planar simple, mientras que puede resolverse en tiempo lineal cuando es un grafo 1-planar simple, para cualquier valor de . Nuestros resultados contribuyen a los crecientes campos de la planaridad híbrida y del dibujo de grafos más allá de la planaridad.

Otros recursos que podrían interesarte

Temas Virtualpro