|国家预印本平台
首页|Efficiently Partitioning the Edges of a 1-Planar Graph into a Planar Graph and a Forest

Efficiently Partitioning the Edges of a 1-Planar Graph into a Planar Graph and a Forest

Efficiently Partitioning the Edges of a 1-Planar Graph into a Planar Graph and a Forest

来源:Arxiv_logoArxiv
英文摘要

1-planar graphs are graphs that can be drawn in the plane such that any edge intersects with at most one other edge. Ackerman showed that the edges of a 1-planar graph can be partitioned into a planar graph and a forest, and claims that the proof leads to a linear time algorithm. However, it is not clear how one would obtain such an algorithm from his proof. In this paper, we first reprove Ackerman's result (in fact, we prove a slightly more general statement) and then show that the split can be found in linear time by using an edge-contraction data structure by Holm et al.

Therese Biedl、Sam Barr

数学

Therese Biedl,Sam Barr.Efficiently Partitioning the Edges of a 1-Planar Graph into a Planar Graph and a Forest[EB/OL].(2021-04-25)[2025-08-02].https://arxiv.org/abs/2104.12286.点此复制

评论