Recognizing Optimal 1-Planar Graphs in Linear Time
arXiv:1602.08022 · doi:10.1007/s00453-016-0226-8
Abstract
A graph with n vertices is 1-planar if it can be drawn in the plane such that each edge is crossed at most once, and is optimal if it has the maximum of 4n-8 edges. We show that optimal 1-planar graphs can be recognized in linear time. Our algorithm implements a graph reduction system with two rules, which can be used to reduce every optimal 1-planar graph to an irreducible extended wheel graph. The graph reduction system is non-deterministic, constraint, and non-confluent.
32 pages, 14 figures. arXiv admin note: substantial text overlap with arXiv:1602.06407
References in corpus (5)
Cited by in corpus (7)
- An annotated bibliography on 1-planarity
- A Survey on Graph Drawing Beyond Planarity
- T-Shape Visibility Representations of 1-Planar Graphs
- On Optimal 2- and 3-Planar Graphs
- A Reduction System for Optimal 1-Planar Graphs
- Map graphs having witnesses of large girth
- Efficiently Partitioning the Edges of a 1-Planar Graph into a Planar Graph and a Forest