D 2007

Approximating the Crossing Number for Graphs close to "Planarity"

HLINĚNÝ, Petr

Základní údaje

Originální název

Approximating the Crossing Number for Graphs close to "Planarity"

Název česky

Aproximace průsečíkového čísla pro grafy "blízké rovinným"

Autoři

Vydání

Dagstuhl, Germany, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Abstracts collection, Dagstuhl Seminar 07281, od s. 6-7, 2 s. 2007

Nakladatel

Schloss Dagstuhl GmbH

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Odkazy

Organizační jednotka

Fakulta informatiky

ISSN

Klíčová slova anglicky

graph; crossing number; almost planar

Štítky

Příznaky

Mezinárodní význam
Změněno: 24. 3. 2010 10:59, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

ORIG CZ

V originále

We show that the graph crossing number can be efficiently approximated up to a constant factor for graphs of bounded degrees that are: almost planar, projective, or toroidal. We ask how much "nonplanarity" of a graph one can allow while still being able to compute or approximate its crossing number efficiently?

Česky

Ukazujeme, že průsečíkové číslo grafu lze aproximovat pro téměř planární, projektivní a toroidální grafy. Zároveň se ptáme, jak mnoho "nerovinnosti" grafu lze povolit, aby stále byl efektivní výpočet možný.

Návaznosti

MSM0021622419, záměr
Název: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy
1M0545, projekt VaV
Název: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky