Inserting Multiple Edges into a Planar Graph

D 2016

Inserting Multiple Edges into a Planar Graph

CHIMANI, Markus and Petr HLINĚNÝ

Basic information

Original name

Inserting Multiple Edges into a Planar Graph

Name in Czech

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

Authors

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

Edition

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

Publisher

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

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

Publication form

electronic version available online

References:

URL

RIV identification code

RIV/00216224:14330/16:00088509

Organization unit

Faculty of Informatics

ISBN

978-3-95977-009-5

ISSN

DOI

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

Keywords in English

crossing number; crossing minimization; planar insertion

Abstract

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.

In Czech

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

Links

GBP202/12/G061, research and development project

Name: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Acronym: CE-ITI)

Investor: Czech Science Foundation

Citovat

CHIMANI, Markus and 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, p. "30:1"-"30:15", 15 pp. ISBN 978-3-95977-009-5. Available from: 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 and 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, p.~''30:1''-''30:15'', 15 pp. ISBN~978-3-95977-009-5. Available from: https://dx.doi.org/10.4230/LIPIcs.SoCG.2016.30.

Detailed Information on Publication Record