Informace o publikaci

Vertex insertion approximates the crossing number of apex graphs

Název česky Vložení vrcholu aproximuje průsečíkové číslo apexových grafů
Autoři

HLINĚNÝ Petr CHIMANI Markus MUTZEL Petra

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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info