Approximating the Crossing Number for Graphs close to "Planarity"

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Název česky	Aproximace průsečíkového čísla pro grafy "blízké rovinným"
Autoři	HLINĚNÝ Petr
Rok publikování	2007
Druh	Článek ve sborníku
Konference	Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Abstracts collection, Dagstuhl Seminar 07281
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	http://drops.dagstuhl.de/portals/index.php?semnr=07281
Obor	Informatika
Klíčová slova	graph; crossing number; almost planar
Popis	Ukazujeme, že průsečíkové číslo grafu lze aproximovat pro téměř planární, projektivní a toroidální grafy. Zároveň se ptáme, jak mnoho "nerovinnosti" grafu lze povolit, aby stále byl efektivní výpočet možný.
Související projekty:	Institut Teoretické Informatiky Vysoce paralelní a distribuované výpočetní systémy