Vertex insertion approximates the crossing number of apex graphs

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	Vložení vrcholu aproximuje průsečíkové číslo apexových grafů
Autoři	HLINĚNÝ Petr CHIMANI Markus MUTZEL Petra
Rok publikování	2012
Druh	Článek v odborném periodiku
Časopis / Zdroj	European Journal of Combinatorics
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
Doi	http://dx.doi.org/10.1016/j.ejc.2011.09.009
Obor	Informatika
Klíčová slova	crossing number; crossing minimization; apex graph
Popis	Dokážeme, že průsečíkové číslo grafu G, který se jedním vrcholem v liší od rovinného, je aproximovatelné s faktorem \Delta(G-v)\cdot d(v)/2 problémem vložení vrcholu v do rovinného nakreslení G.
Související projekty:	Graph Drawings and Representations