En el dibujo de gráficos , la resolución angular del dibujo de un gráfico es el ángulo más agudo formado por dos aristas cualesquiera que se encuentran en un vértice común del dibujo.
Propiedades
Relación con el grado del vértice
Formann et al. (1993) observaron que cada dibujo lineal de un gráfico con grado máximo d tiene una resolución angular como máximo 2π/ d : si v es un vértice de grado d , entonces los bordes incidentes a v dividen el espacio alrededor de v en d cuñas con ángulo total 2π , y la más pequeña de estas cuñas debe tener un ángulo de como máximo 2π/ d . Más claramente, si un gráfico es d - regular , debe tener una resolución angular menor que , porque ésta es la mejor resolución que se puede lograr para un vértice en el casco convexo del dibujo.
Relación con la coloración de gráficos
Como señalan Formann et al. (1993), la mayor resolución angular posible de un gráfico G está estrechamente relacionada con el número cromático del cuadrado G 2 , el gráfico en el mismo conjunto de vértices en el que pares de vértices están conectados por una arista siempre que su distancia en G sea como máximo dos. Si G 2 se puede colorear con χ colores, entonces G se puede dibujar con resolución angular π/ χ − ε , para cualquier ε > 0 , asignando distintos colores a los vértices de un χ -gon regular y colocando cada vértice de G cerca al vértice del polígono del mismo color. Usando esta construcción, demostraron que todo gráfico con grado máximo d tiene un dibujo con resolución angular proporcional a 1/ d 2 . Este límite es casi estricto: utilizaron el método probabilístico para demostrar la existencia de gráficos con grado máximo d cuyos dibujos tienen todos resolución angular .
Existencia de dibujos óptimos.
Formann et al. (1993) proporcionaron un ejemplo mostrando que existen gráficos que no tienen un dibujo que alcance la máxima resolución angular posible; en cambio, estos gráficos tienen una familia de dibujos cuyas resoluciones angulares tienden hacia algún valor límite sin alcanzarlo. Específicamente, exhibieron un gráfico de 11 vértices que tiene dibujos de resolución angular π/3 − ε para cualquier ε > 0 , pero que no tiene un dibujo de resolución angular exactamente π/3 .
Clases especiales de gráficos.
Árboles
Cada árbol se puede dibujar de tal manera que los bordes estén igualmente espaciados alrededor de cada vértice, propiedad conocida como resolución angular perfecta . Además, si los bordes se pueden permutar libremente alrededor de cada vértice, entonces dicho dibujo es posible, sin cruces, con todos los bordes con una longitud unitaria o superior, y con todo el dibujo encajando dentro de un cuadro delimitador de área polinómica . Sin embargo, si el orden cíclico de los bordes alrededor de cada vértice ya está determinado como parte de la entrada al problema, entonces lograr una resolución angular perfecta sin cruces a veces puede requerir un área exponencial. [1]
Gráficos exteriores
La resolución angular perfecta no siempre es posible para los gráficos planos externos , porque los vértices en el casco convexo del dibujo con un grado mayor que uno no pueden tener sus bordes incidentes igualmente espaciados alrededor de ellos. Sin embargo, todo gráfico plano exterior de grado máximo d tiene un dibujo plano exterior con resolución angular proporcional a 1/ d . [2]
Graficos planos
Para gráficos planos con grado máximo d , la técnica de coloración de cuadrados de Formann et al. (1993) proporciona un dibujo con resolución angular proporcional a 1/ d , porque el cuadrado de un gráfico plano debe tener un número cromático proporcional a d . Más precisamente, Wegner conjeturó en 1977 que el número cromático del cuadrado de un gráfico plano es como máximo , y se sabe que el número cromático es como máximo . [3] Sin embargo, los dibujos resultantes de esta técnica generalmente no son planos.
Para algunos gráficos planos, la resolución angular óptima de un dibujo de línea recta plana es O(1/ d 3 ) , donde d es el grado del gráfico. [4] Además, un dibujo de este tipo puede verse obligado a utilizar bordes muy largos, más largos en un factor exponencial que los bordes más cortos del dibujo. Malitz y Papakostas (1994) utilizaron el teorema de empaquetamiento circular y el lema de anillos para demostrar que cada gráfico plano con grado máximo d tiene un dibujo plano cuya resolución angular es, en el peor de los casos, una función exponencial de d , independiente del número de vértices en el gráfico.
Complejidad computacional
Es NP-difícil determinar si una gráfica dada de grado máximo d tiene un dibujo con resolución angular 2π/ d , incluso en el caso especial de que d = 4 . [5] Sin embargo, para ciertas clases restringidas de dibujos, incluidos dibujos de árboles en los que extender las hojas hasta el infinito produce una subdivisión convexa del plano, así como dibujos de gráficos planos en los que cada cara delimitada es un polígono centralmente simétrico, un El dibujo de resolución angular óptima se puede encontrar en tiempo polinomial . [6]
Historia
La resolución angular fue definida por primera vez por Formann et al. (1993).
Aunque originalmente se definió solo para dibujos de gráficos en línea recta, autores posteriores también han investigado la resolución angular de dibujos en los que los bordes son cadenas poligonales, [7] arcos circulares, [8] o curvas spline. [9]
La resolución angular de un gráfico está estrechamente relacionada con su resolución de cruce, el ángulo formado por los cruces en un dibujo del gráfico. En concreto, el dibujo RAC busca conseguir que estos ángulos sean todos rectos , el mayor ángulo de cruce posible. [10]
Notas
^ Duncan y col. (2011); Halupczok y Schulz (2011).
^ Malitz y Papakostas (1994); Garg y Tamassia (1994).
^ Kramer y Kramer (2008); Molloy y Salavatipour (2005).
^ Garg y Tamassia (1994).
^ Formann y col. (1993); Garg y Tamassia (1995).
^ Carlson y Eppstein (2007); Eppstein y Wortman (2011).
^ Kant (1996); Gutwenger y Mutzel (1998).
^ Cheng y otros. (1999); Duncan y cols. (2011).
^ Brandes, Shubina y Tamassia (2000); Finkel y Tamassia (2005).
^ Didimo, Eades y Liotta (2009).
Referencias
Brandes, Ulrik ; Shubina, Galina; Tamassia, Roberto (2000), "Mejora de la resolución angular en visualizaciones de redes geográficas", Visualización de datos 2000: Actas del Simposio conjunto sobre visualización de Eurographics e IEEE TCVG en Ámsterdam, Países Bajos, 29 al 31 de mayo de 2000, doi :10.1007/ 978-3-7091-6783-0_3, ISBN 9783211835159.
Carlson, Josías; Eppstein, David (2007), "Árboles con caras convexas y ángulos óptimos", en Kaufmann, Michael; Wagner, Dorothea (eds.), Proc. 14° Int. Síntoma. Dibujo gráfico (GD'06) , LNCS, vol. 4372, Springer-Verlag, págs. 77–88, arXiv : cs.CG/0607113 , doi : 10.1007/978-3-540-70904-6_9, S2CID 12598338.
Cheng, CC; Duncan, California; Goodrich, MT ; Kobourov, SG (1999), "Dibujo de gráficos planos con arcos circulares", Dibujo de gráficos, Séptimo Simposio Internacional, GD'99, Castillo de Štirín, República Checa, 15 al 19 de septiembre de 1999, Actas , Apuntes de conferencias sobre informática , vol. 1731, Springer-Verlag, págs. 117-126, doi : 10.1007/3-540-46648-7_12.
Dídimo, Walter; Eades, Pedro ; Liotta, Giuseppe (2009), "Dibujo de gráficos con cruces en ángulo recto", Algoritmos y estructuras de datos : 11º Simposio internacional, WADS 2009, Banff, Canadá, 21 al 23 de agosto de 2009. Actas , Lecture Notes in Computer Science, vol. 5664, págs. 206–217, doi :10.1007/978-3-642-03367-4_19.
Duncan, Christian A.; Eppstein, David ; Goodrich, Michael T .; Kobourov, Stephen G.; Nöllenburg, Martin (2011), "Dibujo de árboles con resolución angular perfecta y área polinómica", en Brandes, Ulrik; Cornelsen, Sabine (eds.), Proc. 18° Int. Síntoma. Dibujo de gráficos , Apuntes de conferencias sobre informática, vol. 6502, Springer-Verlag, págs. 183–194, arXiv : 1009.0581 , doi : 10.1007/978-3-642-18469-7_17.
Finkel, Benjamín; Tamassia, Roberto (2005), "Dibujo de gráficos curvilíneas utilizando el método dirigido por la fuerza", Dibujo de gráficos, 12º Simposio Internacional, GD 2004, Nueva York, NY, EE. UU., 29 de septiembre al 2 de octubre de 2004, artículos seleccionados revisados , notas de conferencias en Ciencias de la Computación, vol. 3383, Springer-Verlag, págs. 448–453, doi : 10.1007/978-3-540-31843-9_46.
Formann, M.; Hagerup, T.; Haralambides, J.; Kaufmann, M.; Leighton, pies ; Symvonis, A.; Welzl, E .; Woeginger, G. (1993), "Dibujo de gráficos en el plano con alta resolución", SIAM Journal on Computing , 22 (5): 1035–1052, doi :10.1137/0222063, MR 1237161.
Garg, Ashim; Tamassia, Roberto (1995), "Sobre la complejidad computacional de las pruebas de planaridad rectilínea y ascendente", en Tamassia, Roberto; Tollis, Ioannis (eds.), Dibujo de gráficos , Apuntes de conferencias sobre informática, vol. 894, Springer Berlín / Heidelberg, págs. 286–297, doi : 10.1007/3-540-58950-3_384.
Gutwenger, Carsten; Mutzel, Petra (1998), "Dibujos de polilíneas planas con buena resolución angular", Dibujo de gráficos (Montréal, QC, 1998) , Lecture Notes in Comput. Ciencia, vol. 1547, Berlín: Springer, págs. 167–182, doi :10.1007/3-540-37623-2_13, MR 1717450.
Kant, G. (1996), "Dibujo de gráficos planos utilizando el orden canónico", Algorithmica , 16 (1): 4–32, doi :10.1007/s004539900035, hdl : 1874/16676 , MR 1394492.
Kramer, Florica; Kramer, Horst (2008), "Un estudio sobre la coloración de gráficos a distancia", Matemáticas discretas , 308 (2–3): 422–426, doi :10.1016/j.disc.2006.11.059, MR 2378044.
Malitz, Seth; Papakostas, Achilleas (1994), "Sobre la resolución angular de gráficos planos", Revista SIAM de Matemáticas Discretas , 7 (2): 172–183, doi :10.1137/S0895480193242931, MR 1271989.
Molloy, Michael; Salavatipour, Mohammad R. (2005), "Un límite en el número cromático del cuadrado de un gráfico plano", Journal of Combinatorial Theory , Serie B, 94 (2): 189–213, doi :10.1016/j.jctb. 2004.12.005, hdl : 1807/9473 , señor 2145512.
