2012
Vertex insertion approximates the crossing number of apex graphs
HLINĚNÝ, Petr; Markus CHIMANI a Petra MUTZELZákladní údaje
Originální název
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 ORCID; Markus CHIMANI a Petra MUTZEL
Vydání
European Journal of Combinatorics, Elsevier, 2012, 0195-6698
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Nizozemské království
Utajení
není předmětem státního či obchodního tajemství
Impakt faktor
Impact factor: 0.658
Označené pro přenos do RIV
Ano
Kód RIV
RIV/00216224:14330/12:00057323
Organizační jednotka
Fakulta informatiky
UT WoS
Klíčová slova anglicky
crossing number; crossing minimization; apex graph
Štítky
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 19. 4. 2013 11:10, RNDr. Pavel Šmerk, Ph.D.
V originále
We show that the crossing number of an apex graph, i.e.\ a graph $G$ from which only one vertex $v$ has to be removed to make it planar, can be approximated up to a factor of $\Delta(G-v)\cdot d(v)/2$ by solving the \emph{vertex inserting} problem, i.e.\ inserting a vertex plus incident edges into an optimally chosen planar embedding of a planar graph. Due to a recently developed polynomial algorithm for the latter problem, this establishes the first polynomial fixed-constant approximation algorithm for the crossing number problem of apex graphs with bounded degree.
Česky
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.
Návaznosti
| GEGIG/11/E023, projekt VaV |
|