Inserting Multiple Edges into a Planar Graph

CHIMANI, Markus a Petr HLINĚNÝ. Inserting Multiple Edges into a Planar Graph. Journal of Graph Algorithms and Applications. USA: Brown University, 2023, roč. 27, č. 6, s. 489-522. ISSN 1526-1719. Dostupné z: https://dx.doi.org/10.7155/jgaa.00631.

Základní údaje

• Originální název: Inserting Multiple Edges into a Planar Graph
• Autoři: CHIMANI, Markus (40 Rakousko) a Petr HLINĚNÝ (203 Česká republika, garant, domácí).
• Vydání: Journal of Graph Algorithms and Applications, USA, Brown University, 2023, 1526-1719.

Další údaje

• Originální jazyk: angličtina
• Typ výsledku: Článek v odborném periodiku
• Obor: 10201 Computer sciences, information science, bioinformatics
• Stát vydavatele: Spojené státy
• Utajení: není předmětem státního či obchodního tajemství
• WWW: URL
• Kód RIV: RIV/00216224:14330/23:00131118
• Organizační jednotka: Fakulta informatiky
• Doi: http://dx.doi.org/10.7155/jgaa.00631
• Klíčová slova anglicky: crossing number; multiple edge insertion; fixed parameter tractability
• Štítky: formela-journal
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

Let G be a connected planar (but not yet embedded) graph and F a set of edges with ends in V(G) and not belonging to E(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. A solution to this problem is known to approximate the crossing number of the graph G+F, but unfortunately, finding an exact solution to MEI is NP-hard for general F. The MEI problem is linear-time solvable for the special case of |F|=1 (SODA 01 and Algorithmica), and there is a polynomial-time solvable extension in which all edges of F are incident to a common vertex which is newly introduced into G (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 and JoCO). We present a fixed-parameter algorithm for the MEI problem in the case that G is biconnected, which is extended to also cover the case of connected G with cut vertices of bounded degree. These are the first exact algorithms for the general MEI problem, and they run in time O(|V(G)|) for any constant k.

Návaznosti

• GA20-04567S, projekt VaV: Název: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech

Investor: Grantová agentura ČR, Structure of tractable instances of hard algorithmic problems on graphs