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 | |
Rok publikování | 2012 |
Druh | Článek v odborném periodiku |
Časopis / Zdroj | European Journal of Combinatorics |
Fakulta / Pracoviště MU | |
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: |