Approximating the Crossing Number for Graphs close to "Planarity"

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

HLINĚNÝ Petr

Year of publication 2007
Type Article in Proceedings
Conference Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Abstracts collection, Dagstuhl Seminar 07281
MU Faculty or unit

Faculty of Informatics

Citation
Web http://drops.dagstuhl.de/portals/index.php?semnr=07281
Field Informatics
Keywords graph; crossing number; almost planar
Description We show that the graph crossing number can be efficiently approximated up to a constant factor for graphs of bounded degrees that are: almost planar, projective, or toroidal. We ask how much "nonplanarity" of a graph one can allow while still being able to compute or approximate its crossing number efficiently?
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.