Área (visualización gráfica)

El área en problemas de visualización de gráficos  es una característica numérica de la calidad de la representación gráfica de un gráfico.

La definición de una característica depende del estilo de representación elegido. En una técnica en la que los vértices están dispuestos en una cuadrícula de enteros , el área de una representación se puede definir como el área del cuadro delimitador paralelo más pequeño para la representación, es decir, el producto de la diferencia más grande en las coordenadas de dos vértices y la mayor diferencia en las coordenadas de dos vértices. Para otros estilos de representación, en los que los vértices están espaciados más libremente, la representación se puede escalar para que el par de vértices más cercano tenga una unidad de distancia, después de lo cual el área de representación se puede definir como el cuadro delimitador más pequeño del dibujo. Alternativamente, el área se puede definir como el área del casco convexo de la representación, nuevamente a una escala adecuada [1] .

Límites de polinomios

Para un gráfico plano con vértices dibujados con bordes rectos , el límite óptimo del área de dibujo en el peor de los casos es . Un gráfico de triángulo anidado requiere esta área independientemente de cómo esté anidado el gráfico [2] , y se conocen algunos métodos que permiten dibujar gráficos planos con un área de representación cuadrática máxima [3] [4] . Los árboles binarios y los árboles de grado acotado como caso más general tienen representaciones con área lineal o casi lineal, dependiendo del estilo de dibujo [5] [6] [7] [8] [9] . Cualquier gráfico de plano exterior tiene una representación de plano exterior con segmentos de línea recta como bordes y un área subcuadrática del número de vértices [10] [11] , y si se permiten torceduras o intersecciones , entonces los gráficos de plano exterior tienen representaciones con área casi lineal [12] [ 13] . Sin embargo, la representación de gráficos secuenciales paralelos requiere un área mayor que el producto del valor superpolilogarítmico, incluso si es posible dibujar bordes en forma de líneas quebradas [14] .

Límites exponenciales

Algunos estilos de presentación pueden mostrar un crecimiento de área exponencial , por lo que estos estilos solo pueden ser adecuados para gráficos pequeños. Un ejemplo es la representación plana ascendente de grafos acíclicos dirigidos planos , cuya área para una representación gráfica de vértice puede ser proporcional en el peor de los casos [15] . Incluso los árboles planos pueden requerir un área exponencial si se dibujan con segmentos de línea recta que mantienen un orden cíclico fijo alrededor de cada vértice y deben estar espaciados a distancias iguales alrededor del vértice [16] .

Notas

  1. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 14–15.
  2. ↑ Dolev, Leighton, Trickey, 1984 , pág. 147–161.
  3. ↑ de Fraysseix, Pach y Pollack, 1988 , p. 426–433.
  4. ↑ Schnyder, 1990 , pág. 138–148.
  5. ↑ Crescenzi, Di Battista, Piperno, 1992 , p. 187–200.
  6. ↑ Garg, Goodrich, Tamassia, 1996 , pág. 333–356.
  7. ↑ Chan, 2002 , pág. 1–13.
  8. ↑ Chan, Goodrich, Kosaraju, Tamassia, 2002 , pág. 153–162.
  9. ↑ Garg, Rusu, 2004 , pág. 135–160.
  10. ↑ Garg, Rusu, 2007 , pág. 1116-1140.
  11. ↑ Di Battista, Frati, 2009 , p. 25–53.
  12. ↑ Biedl, 2002 , pág. 54–65.
  13. ↑ Di Giacomo, Didimo, Liotta, Montecchiani, 2013 , pág. 909–916.
  14. ↑ Frati, 2011 , pág. 220–225.
  15. ↑ Di Battista, Tamassia, Tollis, 1992 , p. 381–401.
  16. ↑ Duncan, Eppstein, Goodrich, Kobourov, Nöllenburg, 2013 , pág. 157–182.

Literatura