Search

Your search keyword '"Černý, Jakub"' showing total 5 results
Start Over Author "Černý, Jakub" Publication Type Books
5 results on '"Černý, Jakub"'

5. Improvement on the Decay of Crossing Numbers.

Author

Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Pandu Rangan, C., Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Hong, Seok-Hee, Nishizeki, Takao, Quan, Wu, Černý, Jakub, and Kynčl, Jan

Abstract

We prove that the crossing number of a graph decays in a "continuous fashion" in the following sense. For any ε> 0 there is a δ> 0 such that for n sufficiently large, every graph G with n vertices and m ≥ n1 + ε edges has a subgraph G′ of at most (1 − δ)m edges and crossing number at least . This generalizes the result of J. Fox and Cs. Tóth. [ABSTRACT FROM AUTHOR]

Published
2008
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results