"Springer-Verlag" . "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." . . . "Heraklion, Greece" . "[A976AB59598C]" . "Approximating the Crossing Number of Apex Graphs (poster)" . "RIV/00216224:14330/09:00029117" . . "Mutzel, Petra" . . . "3"^^ . "0302-9743" . . . . . "303920" . "978-3-642-00218-2" . . . . "Hlin\u011Bn\u00FD, Petr" . "14330" . "2008-10-21+02:00"^^ . . . . . "1"^^ . "crossing number; crossing minimization; apex graph"@en . . "3"^^ . . "Symposium Graph Drawing 2008, Lecture Notes in Computer Science" . "Approximating the Crossing Number of Apex Graphs (poster)"@en . "RIV/00216224:14330/09:00029117!RIV11-GA0-14330___" . "Chimani, Markus" . . "Berlin" . "Approximating the Crossing Number of Apex Graphs (poster)" . "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."@en . "Approximating the Crossing Number of Apex Graphs (poster)"@en . . "000264579700041" . "P(1M0545), P(GA201/08/0308), S, Z(MSM0021622419)" .