Inserting Multiple Edges into a Planar Graph

D 2016

Inserting Multiple Edges into a Planar Graph

CHIMANI, Markus a Petr HLINĚNÝ

Základní údaje

Originální název

Inserting Multiple Edges into a Planar Graph

Název česky

Vkládání více hran do rovinného grafu

Autoři

CHIMANI, Markus (276 Německo) a Petr HLINĚNÝ (203 Česká republika, garant, domácí)

Vydání

Germany, 32nd International Symposium on Computational Geometry (SoCG 2016), od s. "30:1"-"30:15", 15 s. 2016

Nakladatel

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

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í

Forma vydání

elektronická verze "online"

Odkazy

URL

Kód RIV

RIV/00216224:14330/16:00088509

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-009-5

ISSN

DOI

http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.30

Klíčová slova anglicky

crossing number; crossing minimization; planar insertion

Štítky

core_A, firank_A, formela-conference

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 27. 4. 2017 07:05, RNDr. Pavel Šmerk, Ph.D.

Anotace

ORIG CZ

V originále

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. We give the first exact algorithm for this problem; it requires only O(|V(G)|) time for any constant k.

Česky

Podáme FPT algoritmus pro problém vložení více hran do rovinného grafu s minimalizací průsečíků.

Návaznosti

GBP202/12/G061, projekt VaV

Název: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Akronym: CE-ITI)

Investor: Grantová agentura ČR, Centrum excelence - Institut teoretické informatiky

Citovat

CHIMANI, Markus a Petr HLINĚNÝ. Inserting Multiple Edges into a Planar Graph. Online. In 32nd International Symposium on Computational Geometry (SoCG 2016). Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2016, s. "30:1"-"30:15", 15 s. ISBN 978-3-95977-009-5. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.SoCG.2016.30.

@inproceedings{1366561,
   author = {Chimani, Markus and Hliněný, Petr},
   address = {Germany},
   booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
   doi = {http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.30},
   keywords = {crossing number; crossing minimization; planar insertion},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Germany},
   isbn = {978-3-95977-009-5},
   pages = {"30:1"-"30:15"},
   publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
   title = {Inserting Multiple Edges into a Planar Graph},
   url = {http://socg2016.cs.tufts.edu/},
   year = {2016}
}

TY  - JOUR
ID  - 1366561
AU  - Chimani, Markus - Hliněný, Petr
PY  - 2016
TI  - Inserting Multiple Edges into a Planar Graph
PB  - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
CY  - Germany
SN  - 9783959770095
KW  - crossing number
KW  - crossing minimization
KW  - planar insertion
UR  - http://socg2016.cs.tufts.edu/
N2  - 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. We give the first exact algorithm for this problem; it requires only O(|V(G)|) time for any constant k.
ER  -

CHIMANI, Markus a Petr HLINĚNÝ. Inserting Multiple Edges into a Planar Graph. Online. In \textit{32nd International Symposium on Computational Geometry (SoCG 2016)}. Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2016, s.~''30:1''-''30:15'', 15 s. ISBN~978-3-95977-009-5. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.SoCG.2016.30.

Podrobný výpis o publikaci