Genus, treewidth, and local crossing number

Vida Dujmovic, David Eppstein, David Wood

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

8 Citations (Scopus)

Abstract

We consider relations between the size, treewidth, and local crossing number (maximum number of crossings per edge) of graphs embedded on topological surfaces. We show that an n-vertex graph embedded on a surface of genus g with at most k crossings per edge has treewidth O(\sqrt{(g+1)(k+1)n}) and layered treewidth O((g+1)k), and that these bounds are tight up to a constant factor. As a special case, the k-planar graphs with n vertices have treewidth O(\sqrt{(k+1)n}) and layered treewidth O(k+1), which are tight bounds that improve a previously known O((k+1)3/4n1/2)O((k+1)3/4n1/2) treewidth bound. Additionally, we show that for g<mg<m, every m-edge graph can be embedded on a surface of genus g with O((m/(g+1))log2g)O((m/(g+1))log2⁡g) crossings per edge, which is tight to a polylogarithmic factor.
Original languageEnglish
Title of host publicationGraph Drawing and Network Visualization: 23rd International Symposium, GD 2015
EditorsEmilio Di Giacomo, Anna Lubiw
Place of PublicationCham Switzerland
PublisherSpringer
Pages87-98
Number of pages12
ISBN (Electronic)9783319272610
ISBN (Print)9783319272603
DOIs
Publication statusPublished - 2015
EventGraph Drawing 2015 - Los Angeles, United States of America
Duration: 24 Sep 201526 Sep 2015
Conference number: 23rd
https://link.springer.com/book/10.1007/978-3-319-27261-0 (Proceedings)

Conference

ConferenceGraph Drawing 2015
Abbreviated titleGD 2015
CountryUnited States of America
CityLos Angeles
Period24/09/1526/09/15
OtherGraph Drawing and Network Visualization: 23rd International Symposium, GD 2015
Internet address

Cite this