Diversos tipos de planaridad de grafos

Desde que fueran introducidos en 1967 por Chartrand y Harary, los grafos periplanos (outerplanar) han sido una de las familias de grafos planos con mayor número de aplicaciones prácticas (que van desde la arquitectura hasta el diseño de circuitos integrados) o en otras disciplinas de las matemáticas (Geometría Computacional y Graph Drawing por nombrar dos de ellas). Sin embargo, esta familia es relativamente pequeña dentro del conjunto de los grafos planos y existen diferentes ámbitos en los que no es
posible directamente su utilización como herramienta. Creemos que es necesario ampliarla en diferentes direcciones para abordar nuevos problemas. Por ello, esta memoria está dedicada a completar y construir diferentes generalizaciones del concepto de grafo periplano.
Uno de los puntos que más hemos desarrollado, ha sido la construcción de algoritmos eficientes que reconocieran las familias de grafos que estudiamos. En principio, esto puede parecer redundante, ya que existen varios algoritmos lineales de planaridad de grafos (Hopcroft y Tarjan; Lempel, Even y Cederbaum; y Nishizeki y Chiba) y cualquiera de ellos podría, en teoría, adaptarse a nuestros fines.
Sin embargo, en la práctica esto no es posible. Los algoritmos de planaridad antes mencionados, debido a su naturaleza, utilizan estructuras de datos muy complicadas y realizan complejas instrucciones que en la práctica hacen que el algoritmo no sea lineal. Por tanto, es necesario buscar métodos más ajustados a nuestros fines que al utilizar operaciones más sencillas, funcionen efectivamente en tiempo lineal.