Inmersiones condicionadas de grafos en superficies y seudosuperficies

Inmersiones condicionadas de grafos en sup er- cies y seudosup ercies. Luis BOZA PRIETO y Eugenio M. FEDRIANI MARTEL L.B.: Departamento de Matematica Aplicada I. Escuela Tecnica Sup erior de Arquitectura. Univ. Sevilla. Avda Reina Mercedes 1, 41012-SEVILLA E-mail: [email protected] E.M.F: Departamento de Economa y Empresa.  Area de Meto dos Cuantitativos. Univ. Pablo de Olavide. Ctra. de Utrera, Km.1. 41013-SEVILLA E-mail: [email protected] Resumen: En este traba jo se pro cede a recapitular resultados cono cidos sobre el problema de caracterizar los grafos que admiten inmersiones en sup ercies y en seudosup er- cies con to dos los vertices en la misma cara y se da una caracterizacion original de los grafos con dicha propiedad en seudosup ercies que surgen de manera natural y que han sido tratadas en la literatura esp ecializada. Se comienza desarrollando algunos conceptos necesarios para la exp osicion de los problemas que se tratan, p ero se sup onen cono cidos otros basicos de la Teora de Grafos. Los resultados relacionados llevan de forma consecuente al planteamiento de otros problemas cuyas resoluciones originales tambien se incluyen. En cuanto a los ob jetivos nales que se pretenden lograr con esta comunicacion, se basan, sobre to do, en aprovechar los resultados obtenidos p or la Teora de Grafos para resolver otros problemas p ertenecientes a otras areas, como la Economa. Se termina exp oniendo un motivo top ologico p or el que estos estudios sobre las inmersiones y las inmersiones p eriS se hallan proximas a la Economa. Palabras clave: Grafo, Inmersion, Seudosup ercie, Periplanaridad. Keywords: Graph, Emb edding, Pseudosurface, Outerplanar. Inmersiones condicionadas de grafos en sup er- cies y seudosup ercies. 1 Intro duccion y preliminares. Desde la primera mitad del siglo XVI I I, los grafos han sido utilizados para mo delizar casi cualquier tip o de problemas; en particular, son esp ecialmente destacables en la actualidad las aplicaciones de la Teora de Grafos en camp os como el dise ~no de circuitos impresos, Arquitectura y Economa. Una forma (top ologica) de denir un grafo es utilizar puntos (que llamaremos vertices o nodos )y lneas que unen esos puntos (a las que se cono ce p or aristas ). Aunque esto no sea una denicion formal para los grafos, ap orta un mo do de representarlos. No obstante, suelen hacerse necesarias otro tip o de deniciones (combinatorias) que pueden ser consultadas en textos relativosalaTeora de Grafos: Harary (1969). Se sup ondra en adelante que el conjunto de vertices es nito y que una arista viene biunvo camente denida p or dos vertices. Hay otras deniciones de grafo que se utilizan asiduamente y de las que se comentara algo mas adelante. Entroncadas con la necesidad de simplicar los problemas, surgen las siguientes: Denicion 1.1. G =( V; A ) es subgrafo de G 0 =( V 0 ;A 0 ) si V  V 0 y A  A 0 . Denicion 1.2. Una sub division de un grafo G es un grafo que se obtiene de G por una sucesion nita de sustituciones de aristas por arcos. Denicion 1.3. Un grafo G 1 es un menor de otro G 2 ,sisepuede l legar desde G 1 hasta G 2 mediante borrado de vertices o aristas o contracciones de aristas. Representar gracamente cada vertice p or un punto y cada arista p or una lnea con extremos en dichos puntos p ermitira decir que un punto p ertenece a un grafo cuando es un vertice o p ertenece a una arista. Esto facilita hablar de grafos homeomorfos entre s y denir una cara como cada una de las comp onentes conexas del complementario del grafo, supuesto este inmerso en una sup ercie o en una seudosup ercie. A las 2-variedades conexas se las suele llamar supercies . Esfera ( S 2 ), toro ( B 0 )y plano proyectivo( P 2 (IR)) son sup ercies. De hecho, a partir de estos tres ejemplos, p o demos construir to das las sup ercies compactas mediante la suma conexa descrita p or Massey (1972). En cuanto a las seudosup ercies, normalmente son sup ercies salvopor unos cuantos puntos (llamados puntos singulares) en los que no existe un entorno homeomorfo a una b ola abierta. Como ejemplos, tenemos los siguientes: Denicion 1.4. Si n 2 IN, B n es la seudosupercie obtenida al contraer a puntos n meridianos distintos de un toro. En general, B n posee n puntos singulares a los que se denotaraenlosucesivo por P 1 ;P 2 ;:::;P n . Ejemplo 1.5. B 0 es el toro, B 1 es el toro estrangulado y B 2 es la `bananas surface' (que se puede obtener al unir dos esferas por dos puntos distintos). u u P 1 P 2 a a b b a a b b u a a P 1 B 0 B 1 B 2 Los lados que se identican estan indicados con la misma letra del alfab eto y con el mismo tip o de echa; la identicacion ha de hacerse de mo do que coincidan los sentidos de las echas. Notese, ademas, que varios puntos p o dran, en este tip o de representaciones de una seudosup ercie, ir al mismo punto tras hacer la identicacion. 2 Inmersiones de grafos. La parte mas imp ortante de la Teora de Grafos es la que se cono ce como Teora de Grafos Top ologicos, que trata de inmersiones de grafos en sup ercies y seudosup er- cies (evitando que se corten las aristas). Precisamente, el resultado matematico mas citado de este siglo (p or encima del Teorema de Go del) es el Teorema de Kuratowski, que caracteriza los grafos planos: Teorema 2.1. [Kuratowski, 1930] Un grafo nito es plano si y solo si no tiene un subgrafo homeomorfo a K 5 o K 3 ; 3 . u u uu u K 5 uu K 3 ; 3 u uu u  Unicamente se cono cen teoremas de este tip o, es decir, que caracterizan grafos con inmersiones en sup ercies, en el caso del plano proyectivo, dado p or Archdeacon y Kuratowski (1981) con una lista de 35 menores prohibidos y otra lista de 103 subgrafos prohibidos. Aunque no se han dado explcitamente otras listas de subgrafos o de menores prohibidos, Rob ertson y Seymour (1990) demuestran que estas son nitas para cualquier sup ercie. Sin embargo,  SiranyGvozdjak (1992) prueban que es innita para la seudosup ercie B 2 . A continuacion, se trata un caso esp ecial de inmersion, la inmersion peri ;es aquella en que to dos los vertices estan en la misma cara. Surgen, as, los grafos p eriplanos, que son los que admiten una inmersion p eri en el plano y que estan caracterizados: Teorema 2.2. [Chartrand y Harary, 1967] Un grafo nito es periplano si y solo si no tiene un subgrafo que sea una subdivision de K 4 o K 2 ; 3 . K 4 K 2 ; 3 s s s s s s ss s El concepto de grafo p eriplano se puede extender a otras sup ercies, con lo que un grafo es periS -representable (o periS ) si admite una inmersion en S con to dos sus vertices en una misma cara. Esta denicion es valida tambien si S es una seudosup ercie. Una vez cono cida la caracterizacion mediante subgrafos prohibidos para los grafos con inmersion en S , se puede obtener la caracterizacion para los grafos con inmersion p eri en S como hace Caceres (1996). As se obtiene la clasicacion de los grafos p eriproyectivos (p eriP 2 IR) Caceres (1996), Archdeacon y otros (1998) y Revuelta (1999) en terminos de 32 menores prohibidos y 45 subgrafos prohibidos. Denicion 2.3. Si k 2 IN nf 0 g ,se conocecomo grafo k -periplano a cualquier grafo que admita una inmersion plana con todos sus vertices en, a lo sumo, k caras. Los grafos 2-p eriplanos tambien fueron caracterizados p or Caceres (1996), Mohar (Archdeacon y otros (1998)) y Revuelta (1999) mediante 38 menores y mediante 56 subgrafos prohibidos. Los 38 menores son K 5 , K 3 ; 3 y los de la siguiente gura: r rr r r r r r r r r r r r r r r r r r r r r r r r r rr r r r r r r r r r r r r r r r r r r r rr r r r r r r r r r r r r r r r r r r r r rr r r r r r r r r r r r r r r r r r r r r r r r r r r r r r rr rr r r r rr r r r r rr r rr r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r rr r r r r r r r r rr r r r r r r r r r r r r rr rr r r r rr r r r rr r r r r r r r r r r r r r r r r r r rr r rr rr r r r r r r rr r r r r r rr rr rr rr r r r rr r r r r r r r r r r rr rr r r r r r r rr r r r r r r r Los 56 subgrafos prohibidos son los 38 menores anteriores mas los 18 siguientes: r r r r r r r r r r r rr r r r r r r r r r r r r r r r r r rr rrr r r rr r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r rrr r r r r r r rrr r r r r r r r r r r r r r r r rrr r r r rr r r r rr r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r rr r r r r r r r r rr r r r En la siguiente seccion se relacionan los grafos 2-p eriplanos con los grafos p eri en ciertas seudosup ercies, caracterizandose los grafos p eri en algunas seudosup ercies. 3 Grafos p eriB n y generalizaciones de estos. Se prepara ahora el resultado principal de este traba jo, que caracteriza los grafos p eriB 2 : Prop osicion 3.1. Sea G un grafo conexo. Entonces, G es periB 2 si y solo si G es 2 -periplano. Demostracion: Comenzando con la condicion suciente para ser p eriB 2 , sea G un grafo 2p eriplano. Entonces existe una representacion de G en la esfera con to dos los vertices situados en una o dos caras (distinguidas). Para que la representacion sea una inmersion en B 2 solo hay que \p egarle" p or dos puntos distintos una esfera a la que ya tenamos. Basta elegir dichos puntos en el interior top ologico de cada una de las caras distinguidas para que G este inmerso en B 2 con to dos sus vertices en la misma cara. En cuanto a la condicion suciente, sea G un grafo p eriB 2 .Si P 1 y P 2 son los puntos singulares de B 2 y se llama C a la cara en la que estan to dos los vertices de G , se pueden distinguir los siguientes casos exhaustivos y mutuamente excluyentes: 1) Ni P 1 ni P 2 son de G . En este caso, G esta representado en una esfera con to dos los vertices en una o en dos caras (dep endiendo de si ni P 1 ni P 2 son de C o si amb os son de C ). 2) P 1 es de G y P 2 no (o recpro camente). As, en cada una de las dos esferas se tiene representado un grafo p eri-esferico y, p or tanto, p eriplano. Si se unen ambos grafos identicando el P 1 de cada uno de ellos (que se puede sup oner en la cara exterior de amb os) se obtiene un grafo p eriplano, p or lo que tambien es 2-p eriplano. 3) P 1 y P 2 son de G ; sin perdida de generalidad se pueden sup oner vertices. Como ahora C esta totalmente contenida en una de las dos esferas, en la otra no puede hab er otros vertices que P 1 y P 2 . Considerense aqu dos sub casos: a) Si P 1 y P 2 no son adyacentes, se tiene representado G en una esfera con to dos los vertices en una sola cara. b) Si P 1 P 2 son adyacentes, esta arista es lo unico que puede estar fuera de la esfera del resto de los vertices de G . Salvo el caso trivial en que G esta en una sola esfera, C estara en la esfera en la que no este P 1 P 2 . s s P 1 P 2 G s s P 1 P 2 G - Pero, como tanto P 1 como P 2 estan en C , existen arcos de curvaen elinterior top ologico de C que van de P 1 a P 2 y cualquiera de ellos se puede utilizar para armar que G es representable en una esfera con to dos los vertices en dos caras (las que surgen de C al a ~nadir ese arco como P 1 P 2 ). 2 Sigue el caso general: Teorema 3.2. Sea G un grafo. Entonces, G es periB 2 si y solo si G es 2 -periplano. Demostracion: Se pueden eliminar las comp onentes conexas p eriplanas de G sin que eso altere el caracter de 2-p eriplano ni el de p eriB 2 . De este mo do, solo resta notar que un grafo no puede ser 2-p eriplano si p osee mas de una comp onente no p eriplana, con lo que la demostracion de este teorema se reduce a la del caso en que solo existe una comp onente conexa. 2 Corolario 3.3. Sea G un grafo. Son equivalentes: 1. G es periB 2 ; 2. G no tiene como menor a K 5 ,a K 3 ; 3 , ni a uno de los 36 menores anteriormente relacionados; 3. G no tiene ning un subgrafo que sea una subdivision de de uno de los 38 menores anteriores, ni de uno de los 18 subgrafos anteriormente relacionados. Conviene hacer notar aqu que, aunque la lista de subgrafos prohibidos para la planaridad en B 2 es innita, es nita para la p eriB 2 -representabilidad. A partir de los resultados anteriores es facil caracterizar los grafos p eriB n : Teorema 3.4. Sea G un grafo plano. G es periB n con n  2 siysolo si G es 2 -periplano. Demostracion: La primera implicacion resulta identica a la demostracion anterior salvo p orque en lugar de \p egar una esfera p or dos puntos distintos" hay que \p egar una sucesion nita de esferas que estan unidas cada una con la anterior p or un punto y con la p osterior p or otro distinto". En cuanto al recpro co, ahora hay que distinguir si ninguno de los puntos singulares es de G ,sisolo lo es uno o si dos o mas lo son. En cualquier caso, el pro ceso es el mismo de antes. 2 Tamp o co resulta difcil generalizar el Teorema 3.2 considerando los grafos p eriL n; 2 , siendo L n; 2 la seudosup ercie union de n esferas p or dos unicos puntos singulares ( P 1 y P 2 ) que p ertenezcan a to das ellas.