Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Discrete Applied Mat...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Discrete Applied Mathematics
Article
License: Elsevier Non-Commercial
Data sources: UnpayWall
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Discrete Applied Mathematics
Article . 2007
License: Elsevier Non-Commercial
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Discrete Applied Mathematics
Article . 2007 . Peer-reviewed
License: Elsevier Non-Commercial
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 2007
Data sources: zbMATH Open
DBLP
Article
Data sources: DBLP
versions View all 5 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

On k-planar crossing numbers

On \(k\)-planar crossing numbers
Authors: Farhad Shahrokhi; Ondrej Sýkora; László A. Székely; Imrich Vrto;

On k-planar crossing numbers

Abstract

The \(k\)-planar crossing number of a graph \(G\), denoted by \(\text{cr}_k(G)\), is the minimum number of crossings of its edges over all possible drawings of the \(G\) in \(k\) planes. This parameter is related to the thickness parameter: \(\text{cr}_k(G)= 0\) if and only if \(G\) has thickness at most \(k\). Much of the present paper extends ideas of \textit{E. Czabarka, O. Sýkora, L. A. Székely}, and \textit{I. Vrt'o} [Györi, Katona, and Lováz (eds.), More sets, graphs and numbers, Bolyai Society of Mathematical Studies 15, 57--77 (2006; Zbl 1098.05023)], for the case \(k= 2\). The present authors propose algorithms and methods for \(k\)-planar drawings of general graphs, as well as lower bound techniques; they give exact results for \(\text{cr}_k(K_{2k+1,q})\), for \(k\geq 2\); they prove tight bounds for complete graphs; and they study the rectilinear crossing number. There appear to be some typographical difficulties; for example, Figure 1 shows that \(\text{cr}_3(K_{7,30})= 0\), whereas Theorem 3 as written gives the value as 30 (perhaps the final ``\(-1\)'' should be ``\(+1\)'') and on page 1107 the same formula is differently (and ambiguously) written (what role does the ``\(<\)'' play? The sign \textit{has} been changed for \(k(2k+1))\).

Keywords

Lower bound, Complete graph, Crossing number, Applied Mathematics, complete bipartite graph, k-planar Crossing number, rectilinear \(k\)-planar crossing number, Rectilinear k-planar crossing number, Planar graphs; geometric and topological aspects of graph theory, Complete bipartite graph, Discrete Mathematics and Combinatorics, crossing number, \(k\)-planar crossing number, lower bound, complete graph

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    10
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Top 10%
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
10
Average
Top 10%
Average
hybrid