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/

Zendy Plus

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

Zendy Tools

Zendy Open

The splitting number of a graph $G=(V,E)$ is the minimum number of vertexsplits required to turn $G$ into a planar graph, where a vertex split removes avertex $v \in V$, introduces two new vertices $v_1, v_2$, and distributes theedges formerly incident to $v$ among its two split copies $v_1, v_2$. Thesplitting number problem is known to be NP-complete. In this paper we shiftfocus to the splitting number of graph drawings in $\mathbb R^2$, where the newvertices resulting from vertex splits can be re-embedded into the existingdrawing of the remaining graph. We first provide a non-uniform fixed-parametertractable (FPT) algorithm for the splitting number problem (without drawings).Then we show the NP-completeness of the splitting number problem for graphdrawings, even for its two subproblems of (1) selecting a minimum subset ofvertices to split and (2) for re-embedding a minimum number of copies of agiven set of vertices. For the latter problem we present an FPT algorithmparameterized by the number of vertex splits. This algorithm reduces to abounded outerplanarity case and uses an intricate dynamic program on asphere-cut decomposition.

Planarizing Graphs and their Drawings by Vertex Splitting