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
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
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.
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.