Approximating the Crossing Number for Graphs close to "Planarity"
| Authors | |
|---|---|
| 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 | |
| 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: |