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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

A topological graph is a graph drawn in the plane. A topological graph is k-plane, (ku003e0), if each edge is crossed at most k times. We study the problem of partitioning the edges of a k-plane graph such that each partite set forms a graph with a simpler structure. While this problem has been studied for (k=1), we focus on optimal 2-plane and 3-plane graphs, which are 2-plane and 3-plane graphs with maximum density. We prove the following results. (i) It is not possible to partition the edges of a simple optimal 2-plane graph G into a 1-plane graph and a forest, while (ii) an edge partition of G formed by a 1-plane graph and two plane forests always exists and can be computed in linear time. (iii) We describe efficient algorithms to partition the edges of G into a 1-plane graph and a plane graph with maximum vertex degree 12, or with maximum vertex degree 8 if G is such that its crossing-free edges form a graph with no separating triangles. (iv) We exhibit an infinite family of simple optimal 2-plane graphs such that in any edge partition composed of a 1-plane graph and a plane graph, the plane graph has maximum vertex degree at least 6. (v) We show that every optimal 3-plane graph whose crossing-free edges form a biconnected graph can be decomposed into a 2-plane graph and two plane forests.

Edge Partitions of Optimal 2-plane and 3-plane Graphs