Home  Issues  About JGAA  Instructions for Authors 
Special Issue on Parameterized and Approximation Algorithms in Graph Drawing
DOI: 10.7155/jgaa.00631
Inserting Multiple Edges into a Planar Graph
Vol. 27, no. 6, pp. 489522, 2023. Regular paper.
Abstract 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 NPhard for general $F$.
The MEI problem is lineartime solvable for the special case of $F=1$ (SODA 01 and Algorithmica),
and there is a polynomialtime 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 fixedparameter 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$.
This work is licensed under the terms of the CCBY license.

Submitted: May 2022.
Reviewed: October 2022.
Revised: December 2022.
Accepted: April 2023.
Final: April 2023.
Published: July 2023.

Journal Supporters
