Inserting Multiple Edges into a Planar Graph

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

CHIMANI Markus HLINĚNÝ Petr

Year of publication 2023
Type Article in Periodical
Magazine / Source Journal of Graph Algorithms and Applications
MU Faculty or unit

Faculty of Informatics

Citation
web https://jgaa.info/accepted/2023/631.pdf
Doi http://dx.doi.org/10.7155/jgaa.00631
Keywords crossing number; multiple edge insertion; fixed parameter tractability
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.