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. 489-522, 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 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$.
This work is licensed under the terms of the CC-BY license.
|
Submitted: May 2022.
Reviewed: October 2022.
Revised: December 2022.
Accepted: April 2023.
Final: April 2023.
Published: July 2023.
|
Journal Supporters
|