| Full text | |
| Author(s): |
Total Authors: 3
|
| Affiliation: | [1] Univ Waterloo, Waterloo, ON - Canada
[2] Univ Estadual Campinas, Campinas - Brazil
Total Affiliations: 2
|
| Document type: | Journal article |
| Source: | GRAPHS AND COMBINATORICS; AUG 2021. |
| Web of Science Citations: | 0 |
| Abstract | |
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) | |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 15/04385-0 - Crossing number of graphs in arbitrary surfaces |
| Grantee: | André Carvalho Silva |
| Support Opportunities: | Scholarships abroad - Research Internship - Doctorate |
| FAPESP's process: | 14/14375-9 - The Crossing Number of Graphs |
| Grantee: | André Carvalho Silva |
| Support Opportunities: | Scholarships in Brazil - Doctorate |