Inserting Multiple Edges into a Planar Graph

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F16%3A00088509" target="_blank" >RIV/00216224:14330/16:00088509 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.30" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.30</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.30" target="_blank" >10.4230/LIPIcs.SoCG.2016.30</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Inserting Multiple Edges into a Planar Graph

Popis výsledku v původním jazyce

Let G be a connected planar (but not yet embedded) graph and F a set of additional edges not in G. The multiple edge insertion problem (MEI) asks for a drawing of G+F with the minimum number of pairwise edge crossings, such that the subdrawing of G is plane. An optimal solution to this problem is known to approximate the crossing number of the graph G+F. Finding an exact solution to MEI is NP-hard for general F, but linear time solvable for the special case of |F|=1 [Gutwenger et al, SODA 2001/Algorithmica] and polynomial time solvable when all of F are incident to a new vertex [Chimani et al, SODA 2009]. The complexity for general F but with constant k=|F| was open, but algorithms both with relative and absolute approximation guarantees have been presented [Chuzhoy et al, SODA 2011], [Chimani-Hlineny, ICALP 2011]. We show that the problem is fixed parameter tractable (FPT) in k for biconnected G, or if the cut vertices of G have bounded degrees.

Název v anglickém jazyce

Inserting Multiple Edges into a Planar Graph

Popis výsledku anglicky

Let G be a connected planar (but not yet embedded) graph and F a set of additional edges not in G. The multiple edge insertion problem (MEI) asks for a drawing of G+F with the minimum number of pairwise edge crossings, such that the subdrawing of G is plane. An optimal solution to this problem is known to approximate the crossing number of the graph G+F. Finding an exact solution to MEI is NP-hard for general F, but linear time solvable for the special case of |F|=1 [Gutwenger et al, SODA 2001/Algorithmica] and polynomial time solvable when all of F are incident to a new vertex [Chimani et al, SODA 2009]. The complexity for general F but with constant k=|F| was open, but algorithms both with relative and absolute approximation guarantees have been presented [Chuzhoy et al, SODA 2011], [Chimani-Hlineny, ICALP 2011]. We show that the problem is fixed parameter tractable (FPT) in k for biconnected G, or if the cut vertices of G have bounded degrees.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

32nd International Symposium on Computational Geometry (SoCG 2016)

ISBN

9783959770095

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

15

Strana od-do

"30:1"-"30:15"

Název nakladatele

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Místo vydání

Germany

Místo konání akce

Boston, USA

Datum konání akce

14. 6. 2016

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—