Dibujos Ortogonales Más Compactos al Permitir Dobles Adicionales
Autores: Jünger, Michael; Mutzel, Petra; Spisla, Christiane
Idioma: Inglés
Editor: MDPI
Año: 2018
Acceso abierto
Artículo científico
2018
Dibujos Ortogonales Más Compactos al Permitir Dobles Adicionales
Categoría
Gestión y administración
Subcategoría
Gestión de la tecnología y la inovación
Palabras clave
Dibujos
Ortogonal
Compactación
Borde
Geometría
Modelo de flujo de red
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 1
Citaciones: Sin citaciones
Compactar dibujos ortogonales es una tarea desafiante. Por lo general, los algoritmos intentan calcular dibujos con un área pequeña o una longitud total de aristas reducida, mientras preservan la forma ortogonal subyacente. Sugerimos una relajación moderada del problema de compactación ortogonal, a saber, el problema de compactación de aristas flexibles monótonas unidimensionales con geometría de estrella de vértices fijos. Además, mostramos que este problema se puede resolver en tiempo polinómico utilizando un modelo de flujo de red. Una evaluación experimental muestra que al permitir curvas adicionales se podría reducir la longitud total de las aristas y el área del dibujo.
Descripción
Compactar dibujos ortogonales es una tarea desafiante. Por lo general, los algoritmos intentan calcular dibujos con un área pequeña o una longitud total de aristas reducida, mientras preservan la forma ortogonal subyacente. Sugerimos una relajación moderada del problema de compactación ortogonal, a saber, el problema de compactación de aristas flexibles monótonas unidimensionales con geometría de estrella de vértices fijos. Además, mostramos que este problema se puede resolver en tiempo polinómico utilizando un modelo de flujo de red. Una evaluación experimental muestra que al permitir curvas adicionales se podría reducir la longitud total de las aristas y el área del dibujo.