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

In the area of graph drawing, the One-Sided Crossing Minimization Problem(OSCM) is defined on a bipartite graph with both vertex sets aligned parallelto each other and all edges being drawn as straight lines. The task is to finda permutation of one of the node sets such that the total number of alledge-edge intersections, called crossings, is minimized. Usually, the degree ofthe nodes of one set is limited by some constant k, with the problem thenabbreviated to OSCM-k.  In this work, we study an online variant of this problem, in which one of thenode sets is already given. The other node set and the incident edges arerevealed iteratively and each node has to be inserted into placeholders, whichwe call slots. The goal is again to minimize the number of crossings in thefinal graph. Minimizing crossings in an online way is related to the moreempirical field of dynamic graph drawing. Note the slotted OSCM problem makesinstances harder to solve for an online algorithm but in the offline case it isequivalent to the version without slots.  We show that the online slotted OSCM-k is not competitive for any k greateror equal 2 and subsequently limit the graph class to that of 2-regular graphs,for which we show a lower bound of 4/3 and an upper bound of 5 on thecompetitive ratio.

The Slotted Online One-Sided Crossing Minimization Problem on 2-Regular Graphs