Inserting Multiple Edges into a Planar Graph

Markus Chimani ; Petr Hliněný

Journal of Graph Algorithms and Applications, Special Issue on Parameterized and Approximation Algorithms in Graph Drawing , Tome 27 (2023) no. 6, pp. 489-522.

Résumé

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$.

Détail

DOI : 10.7155/jgaa.00631

Keywords: crossing number, edge insertion, parameterized complexity, path homotopy, funnel algorithm