Approximating the Crossing Number of Apex Graphs

HLINĚNÝ, Petr, Markus CHIMANI and Petra MUTZEL. Approximating the Crossing Number of Apex Graphs. In Symposium Graph Drawing 2008, Lecture Notes in Computer Science. 5417th ed. Berlin: Springer Verlag, 2009, p. 432-434. ISBN 978-3-642-00218-2. Available from: https://dx.doi.org/10.1007/978-3-642-00219-9_42.

Basic information

Original name

Approximating the Crossing Number of Apex Graphs

Name in Czech

Aproximace průsečíkového čísla apexových grafů

Authors

HLINĚNÝ, Petr (203 Czech Republic, guarantor, belonging to the institution), Markus CHIMANI (276 Germany) and Petra MUTZEL (276 Germany)

Edition

5417. vyd. Berlin, Symposium Graph Drawing 2008, Lecture Notes in Computer Science, p. 432-434, 3 pp. 2009

Publisher

Springer Verlag

---

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Greece

Confidentiality degree

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

Publication form

printed version "print"

References:

conference

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/09:00065851

Organization unit

Faculty of Informatics

ISBN

978-3-642-00218-2

ISSN

DOI

http://dx.doi.org/10.1007/978-3-642-00219-9_42

UT WoS

000264579700041

Keywords in English

crossing number; crossing minimization; apex graph

Tags

apex graph, crossing minimization, crossing number

Tags

International impact, Reviewed

---

Abstract

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.

In Czech

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.

---

Links

GA201/08/0308, research and development project	Name: Využití strukturálních a "šířkových" parametrů v kombinatorice a algoritmické složitosti Investor: Czech Science Foundation, Utilization of Structural and Width Parametres in Combinatorics and Algorithmic Complexity
MSM0021622419, plan (intention)	Name: Vysoce paralelní a distribuované výpočetní systémy Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems
1M0545, research and development project	Name: Institut Teoretické Informatiky Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science