| 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.
|
