|
|||||
|
|
On k-planar crossing numbers |
|
| Authors: | Farhad Shahrokhi Ondrej Sýkora László A Székely Imrich Vrt’o |
| Institution: | a Department of Computer Science, University of North Texas, P.O. Box 13886, Denton, TX 76203-3886, USA b Department of Computer Science, Loughborough University, Loughborough, LE11 3TU, UK c Department of Mathematics, University of South Carolina, Columbia, SC 29208, USA d Institute of Mathematics, Slovak Academy of Sciences, Dúbravská 9, 841 04 Bratislava, Slovak Republic |
| Abstract: | The k-planar crossing number of a graph is the minimum number of crossings of its edges over all possible drawings of the graph in k planes. We propose algorithms and methods for k-planar drawings of general graphs together with lower bound techniques. We give exact results for the k-planar crossing number of K2k+1,q, for k?2. We prove tight bounds for complete graphs. We also study the rectilinear k-planar crossing number. |
| Keywords: | Complete graph Complete bipartite graph Crossing number k-planar Crossing number Lower bound Rectilinear k-planar crossing number |
| 本文献已被 ScienceDirect 等数据库收录！ | |