Campus Units

Mathematics

Document Type

Article

Publication Version

Submitted Manuscript

Publication Date

2016

Journal or Book Title

Journal of Graph Theory

Volume

84

First Page

552

Last Page

565

DOI

10.1002/jgt.22041

Abstract

The crossing number cr(G) of a graph G is the minimum number of crossings in a drawing of G in the plane with no more than two edges intersecting at any point that is not a vertex. The rectilinear crossing number of G is the minimum number of crossings in a such drawing of Gwith edges as straight line segments. Zarankiewicz proved in 1952 that . We generalize the upper bound . to . and prove . We also show that for n large enough, and , with the tighter rectilinear lower bound established through the use of flag algebras. A complete multipartite graph is balanced if the partite sets all have the same cardinality. We study asymptotic behavior of the crossing number of the balanced complete r-partite graph. Richter and Thomassen proved in 1997 that the limit as of over the maximum number of crossings in a drawing of exists and is at most . We define and show that for a fixed r and the balanced complete r-partite graph, is an upper bound to the limit superior of the crossing number divided by the maximum number of crossings in a drawing.

Comments

This is a manuscript of an article from the Journal of Graph Theory 84 (2017): 552, doi:10.1002/jgt.22041. Posted with permission.

Copyright Owner

Wiley Periodicals, Inc.

Language

en

File Format

application/pdf

Published Version

Share

COinS