Bounding the Number of Non-duplicates of the q-Side in Simple Drawings of K-p,K-q

Autor(es)

Richter, R. Bruce ^[1] ; Silva, Andre C. ; Lee, Orlando ^[2]

Afiliação do(s) autor(es)

^[1] Univ Waterloo, Waterloo, ON - Canada

^[2] Univ Estadual Campinas, Campinas - Brazil

• Tipo de documento: Artigo Científico
• Fonte: GRAPHS AND COMBINATORICS; AUG 2021.
• Citações Web of Science: 0

Resumo

The number Zon(n) := left perpendicular n/2 right perpendicular left perpendicular (n - 1)/2 right perpendicular is the smallest number of crossings in a simple planar drawing of K-2,K-n in which both vertices on the 2-side have the same clockwise rotation. For two vertices u, v on the q-side of a simple drawing of K-p,K-q, let cr(D)(u, v) denote the total number of crossings that edges incident with u have with edges incident with v. We show that in any simple drawing D of K-p,K-q in a surface Sigma the number of pairs of vertices on the q-side of K-p,K-q having cr(D)(u, v) < Z(p) is bounded as a function of p and Sigma. As a consequence, we also show that, for a fixed integer p and surface Sigma, there exists a finite set of drawings D(p, Sigma) of complete bipartite graphs such that, for each q, a crossing-minimal drawing of K-p,K-q can be obtained by ``duplicating vertices{''} in some drawing from D(p, Sigma). (AU)

• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 15/04385-0 - Número de cruzamentos de grafos em superfícies arbitrárias
• Beneficiário: André Carvalho Silva
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado
• Processo FAPESP: 14/14375-9 - Número de Cruzamentos de um Grafo
• Beneficiário: André Carvalho Silva
• Modalidade de apoio: Bolsas no Brasil - Doutorado