Pach, János and Székely, László A. and Tóth, Csaba D. and Tóth, Géza (2018) Note on k-planar crossing numbers. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 68. pp. 2-6. ISSN 0925-7721
|
Text
1611.05746v1.pdf Download (129kB) | Preview |
Abstract
The crossing number CR(G) of a graph G=(V,E) is the smallest number of edge crossings over all drawings of G in the plane. For any k≥1, the k-planar crossing number of G, CRk(G), is defined as the minimum of CR(G0)+CR(G1)+…+CR(Gk−1) over all graphs G0,G1,…,Gk−1 with ∪i=0 k−1Gi=G. It is shown that for every k≥1, we have CRk(G)≤([Formula presented]−[Formula presented])CR(G). This bound does not remain true if we replace the constant [Formula presented]−[Formula presented] by any number smaller than [Formula presented]. Some of the results extend to the rectilinear variants of the k-planar crossing number. © 2017 Elsevier B.V.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Graph theory; Graph G; Graph decompositions; Geometric graphs; Edge crossing; Computational geometry; Applications; Graph decomposition; Geometric graph; Crossing number |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 05 Feb 2018 12:55 |
| Last Modified: | 05 Feb 2018 12:55 |
| URI: | http://real.mtak.hu/id/eprint/73903 |
Actions (login required)
 |
Edit Item |
