Mejorando las representaciones compactas de grafos planares.

Abstract

La capacidad de los computadores de procesar y almacenar información ha crecido exponencialmente con el pasar de los años. Sin embargo, el volumen de datos generados y capturados por la humanidad igualmente está creciendo de manera exponencial, e incluso a tasas mayores que el avance de la tecnología, lo que ha motivado el surgimiento de técnicas de procesamiento y almacenamiento de datos cada vez más sofisticadas. Una de las soluciones existentes para esta problemática es el uso de estructuras de datos compactas [25], las cuales reducen el espacio utilizado para almacenar ciertos datos, a la vez que proveen soporte para ciertas operaciones, aunque generalmente con un trade-off entre espacio y velocidad en las operaciones. Esto es importante no sólo por el crecimiento en la generación de datos, sino también, porque cada vez se trata de procesar datos en dispositivos más pequeños, pero cercanos a donde los datos son producidos; esto es el caso en el paradigma edge computing [10, 4], debido a que la tendencia es a utilizar dispositivos más portables y con capacidad limitada de almacenamiento como lo son celulares inteligentes, sensores para IoT o wearables. Las estructuras de datos compactas ya se han utilizado exitosamente en dominios tales como Sistemas de Información Geográfica [13, 12], bioinformática [8, 33], recuperación de información [2, 1], por nombrar algunos ejemplos.