{"id":246,"date":"2014-12-11T18:23:17","date_gmt":"2014-12-11T20:23:17","guid":{"rendered":"http:\/\/www.ime.usp.br\/~tcco\/?page_id=246"},"modified":"2014-12-11T19:58:54","modified_gmt":"2014-12-11T21:58:54","slug":"crossing-number-workshop","status":"publish","type":"page","link":"https:\/\/www.ime.usp.br\/~tcco\/crossing-number-workshop\/","title":{"rendered":"Workshop on Topological Graph Theory: Crossing Number"},"content":{"rendered":"<p style=\"text-align: left;\">December 16, 2014<\/p>\n<p style=\"text-align: left;\">Auditorium of <a href=\"http:\/\/www.numec.prp.usp.br\/\">NUMEC (N\u00facleo de Apoio \u00e0 Pesquisa em Modelagem Estoc\u00e1stica e Complexidade)<\/a><br \/>\nat the <a href=\"http:\/\/www.ime.usp.br\">Institute of Mathematics and Statistics of the University of S\u00e3o Paulo &#8211; IME-USP<\/a><\/p>\n<p><br \/>\n\n<table id=\"tablepress-4\" class=\"tablepress tablepress-id-4\">\n<thead>\n<tr class=\"row-1\">\n\t<th class=\"column-1\" style=\"width:20%;\"><strong>Time<\/strong><\/th><th class=\"column-2\" style=\"width:80%;\"><strong>Activity<\/strong><\/th>\n<\/tr>\n<\/thead>\n<tbody class=\"row-striping\">\n<tr class=\"row-2\">\n\t<td class=\"column-1\">9:30&ndash;10:15<\/td><td class=\"column-2\"><a href=\"#rvpocai\"><strong>Graph Embeddings and Crossing Number<\/strong><\/a><br \/>Rafael Veiga Pocai<\/td>\n<\/tr>\n<tr class=\"row-3\">\n\t<td class=\"column-1\">10:15&ndash;11:00<\/td><td class=\"column-2\"><a href=\"#gsalar\"><strong>Permutations and book embeddings of graphs<\/strong><\/a><br \/>Gelasio Salazar<\/td>\n<\/tr>\n<tr class=\"row-4\">\n\t<td class=\"column-1\">11:00&ndash;14:00<\/td><td class=\"column-2\">Lunch<\/td>\n<\/tr>\n<tr class=\"row-5\">\n\t<td class=\"column-1\">14:00&ndash;14:45<\/td><td class=\"column-2\"><a href=\"#israel\"><strong>Pseudolinear crossing number and rectilinear crossing number<\/strong> <\/a><br \/>C\u00e9sar Hern\u00e1ndez-V\u00e9lez<\/td>\n<\/tr>\n<tr class=\"row-6\">\n\t<td class=\"column-1\">14:45&ndash;15:30<\/td><td class=\"column-2\"><a href=\"#luerbio\"><strong>Upperbounds for crossing numbers of the \\(n\\)-cube<\/strong> <\/a><br \/>Luerbio Faria<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<!-- #tablepress-4 from cache --><\/p>\n<h2>Abstracts of the Talks<\/h2>\n<ul>\n<li>\n<div class=\"lyon-abstract\"><strong><a name=\"rvpocai\">Graph Embeddings and Crossing Number<\/a><\/strong><br \/>\n\tRafael Veiga Pocai<br \/>\n        Instituto de Matem\u00e1tica e Estat\u00edstica, Universidade de S\u00e3o Paulo<\/p>\n<p>Abstract: In this talk, we will discuss two optimization problems relating graphs and surfaces: the genus problem and the crossing number problem. These problems ask for &#8220;the best&#8221;, or &#8220;the simplest&#8221; way of drawing a graph on a surface. We will present their definitions, some special cases and intractability results.<\/p>\n<\/li>\n<li>\n<div class=\"lyon-abstract\"><strong><a name=\"gsalar\">Permutations and book embeddings of graphs<\/a><\/strong><br \/>\n        Gelasio Salazar<br \/>\n        Instituto de F\u00edsica, Universidad Aut\u00f3noma de San Luis Potos\u00ed<\/p>\n<p>Abstract: Some of the most natural and basic questions in combinatorics can be posed as problems on (decompositions of) permutations. For instance: given a permutation, how can it be efficiently decomposed into (many) subpermutations with certain properties? Or, given several permutations: which are the longest  subpermutations (or subpatterns) that they have in common? In this talk we&#8217;ll review some of these problems, and explore their relationship to another hard combinatorial problem: how to embed a graph into a book with &#8220;few&#8221; pages. This is joint work with Jozsef Balogh.<\/p>\n<\/div>\n<\/li>\n<li>\n<div class=\"lyon-abstract\"><strong><a name=\"israel\">Pseudolinear crossing number and rectilinear crossing number<\/a><\/strong><br \/>\n        C\u00e9sar Hern\u00e1ndez-V\u00e9lez<br \/>\n        Instituto de Matem\u00e1tica e Estat\u00edstica, Universidade de S\u00e3o Paulo<\/p>\n<p>Abstract: A drawing of a graph is pseudolinear if there is a pseudoline arrangement such that each pseudoline contains exactly one edge of the drawing. The pseudolinear crossing number of a graph G is the minimum number of pairwise crossings of edges in a pseudolinear drawing of G. We establish several facts on the pseudolinear crossing number, including its relationship to the usual crossing number and to the rectilinear crossing number. This investigation was motivated by open questions and issues raised by Marcus Schaefer in his comprehensive survey of the many variants of the crossing number of a graph. Joint work with Jes\u00fas Lea\u00f1os and Gelasio Salazar.<\/p>\n<\/div>\n<\/li>\n<li>\n<div class=\"lyon-abstract\"><strong><a name=\"luerbio\">Upperbounds for crossing numbers of the \\(n\\)-cube<\/a><\/strong><br \/>\n        Luerbio Faria<br \/>\n        Instituto de Matem\u00e1tica e Estat\u00edstica, Universidade do Estado do Rio de Janeiro<\/p>\n<p>Abstract: The crossing number \\(cr(G)\\) of \\(G\\) is the minimum number of crossings in a drawing of \\(G\\) in the plane. The <i>rectilinear<\/i> crossing number \\(\\overline{cr}(G)\\) of \\(G\\) is the  minimum number of crossings in a drawing of \\(G\\) in the plane with straight line segments at the place of the edges of \\(G\\). The <i>2-page<\/i> crossing number \\(cr_2(G)\\) of \\(G\\) is the minimum number of crossings in a drawing of \\(G\\) into 2 semiplanes where the vertices of \\(G\\) belong to a straight  line bounding the semiplanes. Very little is known about crossing  numbers of classes of graphs. The \\(n\\)-cube graph \\(Q_n\\) has \\(|V(Q_n)| = 2^n\\), there is a 1-1 function between \\(V(Q_n)\\) and the set of binary \\(n\\)-tuples. An edge \\(uv\\) is in \\(E(Q_n)\\)  iff the difference, \\(diff(u,v)=1\\), between \\(u\\) and \\(v\\) has  exactly one bit. The only known values for crossing numbers of cubes are \\(cr(Q_i)=\\overline{cr}(Q_i)=cr_2(Q_i)=0, i=0,1,2,3\\)  and \\(cr(Q_4)=\\overline{cr}(Q_4)=cr_2(Q_4)=8\\). It is known that \\(cr(Q_n)=\\overline{cr}(Q_n)=cr_2(Q_n)=\\Theta(4^n)\\). And the  remaining are upperbounds. In this talk we present some results about upperbounds for some crossing numbers of the \\(n\\)-cube graph.<\/p>\n<\/div>\n<\/li>\n<\/ul>\n<h3>Acknowledgements<\/h3>\n<p>We gratefully acknowledge the support of <a href=\"http:\/\/projetos.numec.prp.usp.br\/MaCLinC\">MaCLinC<\/a> and <a href=\"http:\/\/www.numec.prp.usp.br\/\">NUMEC<\/a> for hosting this event.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>December 16, 2014 Auditorium of NUMEC (N\u00facleo de Apoio \u00e0 Pesquisa em Modelagem Estoc\u00e1stica e Complexidade) at the Institute of Mathematics and Statistics of the University of S\u00e3o Paulo &#8211; IME-USP Abstracts of the Talks Graph Embeddings and Crossing Number Rafael Veiga Pocai Instituto de Matem\u00e1tica e Estat\u00edstica, Universidade de S\u00e3o Paulo Abstract: In this [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"open","template":"page-templates\/full-width.php","meta":{"footnotes":""},"class_list":["post-246","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.ime.usp.br\/~tcco\/wp-json\/wp\/v2\/pages\/246"}],"collection":[{"href":"https:\/\/www.ime.usp.br\/~tcco\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.ime.usp.br\/~tcco\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.ime.usp.br\/~tcco\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ime.usp.br\/~tcco\/wp-json\/wp\/v2\/comments?post=246"}],"version-history":[{"count":6,"href":"https:\/\/www.ime.usp.br\/~tcco\/wp-json\/wp\/v2\/pages\/246\/revisions"}],"predecessor-version":[{"id":255,"href":"https:\/\/www.ime.usp.br\/~tcco\/wp-json\/wp\/v2\/pages\/246\/revisions\/255"}],"wp:attachment":[{"href":"https:\/\/www.ime.usp.br\/~tcco\/wp-json\/wp\/v2\/media?parent=246"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}