Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Note on k-planar crossing numbers
 
conference paper

Note on k-planar crossing numbers

Pach, Janos
•
Szekely, Laszlo A.
•
Toth, Csaba D.
Show more
2018
Computational Geometry-Theory And Applications
Workshop on Exact Crossing Numbers

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(G(0)) + CR(G(1)) + ... + CR(G(k-i)) over all graphs G(0), G(1), ... , G(k-i) with boolean OR(k-1)(i=0) G(i) = G. It is shown that for every k >= 1, we have CRk(G) <= (2/k(2) - 1/k(3)) CR(G). This bound does not remain true if we replace the constant 2/k(2) - 1/k(3) by any number smaller than 1/k(2) Some of the results extend to the rectilinear variants of the k-planar crossing number. (C) 2017 Elsevier B.V. All rights reserved.

  • Details
  • Metrics
Type
conference paper
DOI
10.1016/j.comgeo.2017.06.015
Web of Science ID

WOS:000415778300002

Author(s)
Pach, Janos
Szekely, Laszlo A.
Toth, Csaba D.
Toth, Geza
Date Issued

2018

Publisher

Elsevier Science Bv

Publisher place

Amsterdam

Published in
Computational Geometry-Theory And Applications
Total of pages

5

Volume

68

Start page

2

End page

6

Subjects

Crossing number

•

Graph decomposition

•

Geometric graph

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Event nameEvent placeEvent date
Workshop on Exact Crossing Numbers

Amer Inst Math, Palo Alto, CA

APR 28-MAY 02, 2014

Available on Infoscience
January 15, 2018
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/143960
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés