Full text
| |
| Author(s): |
André Carvalho Silva
Total Authors: 1
|
| Document type: | Doctoral Thesis |
| Press: | Campinas, SP. |
| Institution: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Defense date: | 2018-07-16 |
| Examining board members: |
Orlando Lee;
Jorge Stolfi;
Candida Nunes da Silva;
Cristiane Maria Sato;
Guilherme Oliveira Mota
|
| Advisor: | Orlando Lee |
| Abstract | |
The crossing number of a graph G in a surface ? is the least amount of edge crossings among all possible drawings of G in ?. This thesis deals with two problems on crossing number of graphs: characterization of graphs with crossing number one and determining the crossing number of Kp,q in topological surfaces. For graphs with crossing number one, we present a complete structural characterization. We also show a "practical" algorithm for recognition of such graphs. For the crossing number of Kp,q in surfaces, we show that for a fixed positive integer p and a fixed surface ?, there is a finite set D(p,?) of good drawings of complete bipartite graphs Kp,r (with distinct values of r) such that, for every positive integer q and every good drawing D of Kp,q, there is a good drawing D' of Kp,q obtained from a drawing D'' of D(p,?) by duplicating vertices of D'' and such that the crossing number of D' is at most the crossing number of D. In particular, for any large enough q, there exists some drawing of Kp,q with fewest crossings which can be obtained from a drawing of D(p,?) by duplicating vertices. This extends a result of Christian et. al. for the sphere (AU) | |
| FAPESP's process: | 14/14375-9 - The Crossing Number of Graphs |
| Grantee: | André Carvalho Silva |
| Support Opportunities: | Scholarships in Brazil - Doctorate |