Informace o publikaci
Approximating the Crossing Number of Apex Graphs
Název česky | Aproximace průsečíkového čísla apexových grafů |
---|---|
Autoři | |
Rok publikování | 2009 |
Druh | Článek ve sborníku |
Konference | Symposium Graph Drawing 2008, Lecture Notes in Computer Science |
Fakulta / Pracoviště MU | |
Citace | |
www | conference |
Doi | http://dx.doi.org/10.1007/978-3-642-00219-9_42 |
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: |