{"id":33020,"date":"2018-03-09T09:29:56","date_gmt":"2018-03-09T09:29:56","guid":{"rendered":"https:\/\/www.deberes.net\/tesis\/sin-categoria\/inmersiones-ortogonales-de-grafos-en-superficies-no-planas\/"},"modified":"2018-03-09T09:29:56","modified_gmt":"2018-03-09T09:29:56","slug":"inmersiones-ortogonales-de-grafos-en-superficies-no-planas","status":"publish","type":"post","link":"https:\/\/www.deberes.net\/tesis\/matematicas\/inmersiones-ortogonales-de-grafos-en-superficies-no-planas\/","title":{"rendered":"Inmersiones ortogonales de grafos en superficies no planas"},"content":{"rendered":"<h2>Tesis doctoral de <strong> Mar\u00eda  De Los Angeles Garrido Vizuete <\/strong><\/h2>\n<p>El \u00e1rea de investigaci\u00f3n sobre dibujos de grafos (graph drawing) se ha convertido en un campo extensamente estudiado, constituyendo una interesante conexi\u00f3n entre la computaci\u00f3n y la teor\u00eda de grafos. Dentro de ella, la representaci\u00f3n ortogonal de grafos ocupa un lugar importante por su aplicaci\u00f3n al dise\u00f1o de circuitos vlsi, dando lugar a diversos problemas de optimizaci\u00f3n. esta memoria est\u00e1 dedicada al estudio de las inmersiones ortogonales de grafos en superficies, con el objeto de minimizar el n\u00famero de codos.  motivados por el trabajo de tamassia realizado en el plano, nos planteamos el problema de caracterizar la inmersi\u00f3n ortogonal cil\u00edndrica que presenta el m\u00ednimo n\u00famero de codos, entre todas las equivalentes a las de partida. comenzamos realizando la caracterizaci\u00f3n de la asignaci\u00f3n ortogonal \u00f3ptima, concepto que recoge la informaci\u00f3n de los \u00e1ngulos y codos del trazado, obteni\u00e9ndola en tiempo polinomial.  en el plano, los conceptos de asignaci\u00f3n ortogonal e inmersi\u00f3n en la malla son equivalentes. Sin embargo, en el cilindro la situaci\u00f3n es muy distinta, por lo que realizamos un estudio detallado de la relaci\u00f3n entre ambas estructuras, destacando las diferencias con respecto al plano. Igualmente, dise\u00f1amos algoritmos efectivos que proporcionan inmersiones ortogonales cil\u00edndricas, de forma que el n\u00famero total de codos obtenido constituye una buena aproximaci\u00f3n del valor \u00f3ptimo, guiados por dos enfoques, uno global en el grafo y otro local en cada arista.  desde un punto de vista pr\u00e1ctico, es necesario el estudio de inmersiones ortogonales de grafos en superficies. Este hecho nos conduce al planteamiento de dos importantes problemas en este \u00e1mbito, demostrando su naturaleza np-completa: dada una inmersi\u00f3n en una superficie, decidir si admite una inmersi\u00f3n ortogonal sin codos esencialmente equivalente; y por otra parte, encontrar una superficie en la que un grafo dado admita una inmersi\u00f3n ortogona<\/p>\n<p>&nbsp;<\/p>\n<h3>Datos acad\u00e9micos de la tesis doctoral \u00ab<strong>Inmersiones ortogonales de grafos en superficies no planas<\/strong>\u00ab<\/h3>\n<ul>\n<li><strong>T\u00edtulo de la tesis:<\/strong>\u00a0 Inmersiones ortogonales de grafos en superficies no planas <\/li>\n<li><strong>Autor:<\/strong>\u00a0 Mar\u00eda  De Los Angeles Garrido Vizuete <\/li>\n<li><strong>Universidad:<\/strong>\u00a0 Sevilla<\/li>\n<li><strong>Fecha de lectura de la tesis:<\/strong>\u00a0 18\/07\/1997<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3>Direcci\u00f3n y tribunal<\/h3>\n<ul>\n<li><strong>Director de la tesis<\/strong>\n<ul>\n<li>Alberto M\u00e1rquez P\u00e9rez<\/li>\n<\/ul>\n<\/li>\n<li><strong>Tribunal<\/strong>\n<ul>\n<li>Presidente del tribunal: Juan  Antonio Mesa l\u00f3pez-colmenar <\/li>\n<li>oriol Serra alb\u00f3 (vocal)<\/li>\n<li>julio Jes\u00fas Rubio Garc\u00eda (vocal)<\/li>\n<li>Jos\u00e9 ramon Gomez martin (vocal)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tesis doctoral de Mar\u00eda De Los Angeles Garrido Vizuete El \u00e1rea de investigaci\u00f3n sobre dibujos de grafos (graph drawing) se [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"footnotes":""},"categories":[583,10899,126,10715],"tags":[10831,26592,90446,10901,49621,30341],"class_list":["post-33020","post","type-post","status-publish","format-standard","hentry","category-geometria","category-geometrias-finitas","category-matematicas","category-sevilla","tag-alberto-marquez-perez","tag-jose-ramon-gomez-martin","tag-juan-antonio-mesa-lopez-colmenar","tag-julio-jesus-rubio-garcia","tag-maria-de-los-angeles-garrido-vizuete","tag-oriol-serra-albo"],"_links":{"self":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/33020","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/comments?post=33020"}],"version-history":[{"count":0,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/33020\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/media?parent=33020"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/categories?post=33020"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/tags?post=33020"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}