English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let $G$ be a connected planar (but not yet embedded) graph and $F$ a set ofadditional edges not yet in $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. An optimal solution to this problemapproximates the crossing number of the graph $G+F$.  Finding an exact solution to MEI is NP-hard for general $F$, but linear timesolvable for the special case of $|F|=1$ (SODA01, Algorithmica) or when all of$F$ are incident to a new vertex (SODA09).  The complexity for general $F$ but with constant $k=|F|$ was open, butalgorithms both with relative and absolute approximation guarantees have beenpresented (SODA11, ICALP11). We show that the problem is fixed parametertractable (FPT) in $k$ for biconnected $G$, or if the cut vertices of $G$ havedegrees bounded by a constant. We give the first exact algorithm for thisproblem; it requires only $O(|V(G)|)$ time for any constant $k$.

Inserting Multiple Edges into a Planar Graph