Name
Abstract | ||
|---|---|---|
We show that for each integer g⩾0 there is a constant cg>0 such that every graph that embeds in the projective plane with sufficiently large face–width r has crossing number at least cgr2 in the orientable surface Σg of genus g. As a corollary, we give a polynomial time constant factor approximation algorithm for the crossing number of projective graphs with bounded degree. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.endm.2007.07.037 | Electronic Notes in Discrete Mathematics |
Keywords | DocType | Volume |
crossing number,face–width,projective graph,approximation | Journal | 29 |
Issue | ISSN | Citations |
1 | 1571-0653 | 7 |
PageRank | References | Authors |
0.55 | 13 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Isidoro Gitler | 1 | 29 | 7.03 |
| Petr Hliněný | 2 | 591 | 46.06 |
| Jesús Leaños | 3 | 13 | 4.49 |
| Gelasio Salazar | 4 | 233 | 40.84 |