Approximating the Crossing Number of Apex Graphs

• Název česky: Aproximace průsečíkového čísla apexových grafů
• Autoři: HLINĚNÝ Petr; CHIMANI Markus; MUTZEL Petra
• Rok publikování: 2009
• Druh: Článek ve sborníku
• Konference: Symposium Graph Drawing 2008, Lecture Notes in Computer Science
• Fakulta / Pracoviště MU: Fakulta informatiky
• 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

• Institut Teoretické Informatiky
• Vysoce paralelní a distribuované výpočetní systémy
• Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti