Inserting multiple edges into a planar graph
Autor(en): | Chimani, M. Hliněný, P. |
Herausgeber: | Fekete, S. Lubiw, A. |
Stichwörter: | Algorithms; Approximation algorithms; Computational geometry; Crossing number; Edge insertion; Exact algorithms; Funnel algorithm; Graph theory; Homotopies; Insertion problems; Optimal solutions; Parameterized complexity; Path homotopy; Polynomial approximation; Polynomial-time, Computational complexity; Polynomials, Crossing number | Erscheinungsdatum: | 2016 | Herausgeber: | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing | Journal: | Leibniz International Proceedings in Informatics, LIPIcs | Volumen: | 51 | Startseite: | 30.1--30.15 | Zusammenfassung: | 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 (SODA 01, Algorithmica) and polynomial time solvable when all of F are incident to a new vertex (SODA 09). The complexity for general F but with constant k = |F| was open, but algorithms both with relative and absolute approximation guarantees have been presented (SODA 11, ICALP 11). 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. © Markus Chimani and Petr Hlinìný. |
Beschreibung: | Conference of 32nd International Symposium on Computational Geometry, SoCG 2016 ; Conference Date: 14 June 2016 Through 17 June 2016; Conference Code:122035 |
ISBN: | 9783959770095 | ISSN: | 18688969 | DOI: | 10.4230/LIPIcs.SoCG.2016.30 | Externe URL: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-84976871228&doi=10.4230%2fLIPIcs.SoCG.2016.30&partnerID=40&md5=5978d923d31b7dad87ef6abbafc872e7 |
Zur Langanzeige
Seitenaufrufe
3
Letzte Woche
1
1
Letzter Monat
1
1
geprüft am 03.06.2024