HLINĚNÝ, Petr. Approximating the Crossing Number for Graphs close to "Planarity". In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Abstracts collection, Dagstuhl Seminar 07281. Dagstuhl, Germany: Schloss Dagstuhl GmbH, 2007, s. 6-7. ISSN 1862-4405. |
Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{722829, author = {Hliněný, Petr}, address = {Dagstuhl, Germany}, booktitle = {Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Abstracts collection, Dagstuhl Seminar 07281}, keywords = {graph; crossing number; almost planar}, language = {eng}, location = {Dagstuhl, Germany}, pages = {6-7}, publisher = {Schloss Dagstuhl GmbH}, title = {Approximating the Crossing Number for Graphs close to "Planarity"}, url = {http://drops.dagstuhl.de/portals/index.php?semnr=07281}, year = {2007} }
TY - JOUR ID - 722829 AU - Hliněný, Petr PY - 2007 TI - Approximating the Crossing Number for Graphs close to "Planarity" PB - Schloss Dagstuhl GmbH CY - Dagstuhl, Germany KW - graph KW - crossing number KW - almost planar UR - http://drops.dagstuhl.de/portals/index.php?semnr=07281 N2 - 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? ER -
HLINĚNÝ, Petr. Approximating the Crossing Number for Graphs close to ''Planarity''. In \textit{Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Abstracts collection, Dagstuhl Seminar 07281}. Dagstuhl, Germany: Schloss Dagstuhl GmbH, 2007, s.~6-7. ISSN~1862-4405.
|