Recognizing optimal 1-planar graphs in linear time
From MaRDI portal
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.
Recommendations
- Recognizing outer 1-planar graphs in linear time
- Testing maximal 1-planarity of graphs with a rotation system in linear time (extended abstract)
- A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
- A linear-time algorithm for testing outer-1-planarity
- Optimal 1-planar multigraphs
Cites work
- 1-planarity of graphs with a rotation system
- A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
- A linear-time algorithm for testing outer-1-planarity
- Adding one edge to planar graphs makes crossing number and 1-planarity hard
- Algorithms for graphs embeddable with few crossings per edge
- Bemerkungen zu einem Sechsfarbenproblem von G. Ringel
- Density of straight-line 1-planar graph drawings
- Ein Sechsfarbenproblem auf der Kugel
- Enumeration of simple complete topological graphs
- Fan-planarity: properties and complexity
- Fáry's theorem for 1-planar graphs
- Generation of simple quadrangulations of the sphere
- Graphs drawn with few crossings per edge
- Handbook of Graph Grammars and Computing by Graph Transformation
- scientific article; zbMATH DE number 3924797 (Why is no real title available?)
- scientific article; zbMATH DE number 2080088 (Why is no real title available?)
- scientific article; zbMATH DE number 1368469 (Why is no real title available?)
- Map graphs
- On the density of maximal 1-planar graphs
- On the recognition of fan-planar and maximal outer-fan-planar graphs
- On-Line Planarity Testing
- Outer 1-planar graphs
- Parameterized complexity of 1-planarity
- Re-embeddings of Maximum 1-Planar Graphs
- Recognizing hole-free 4-map graphs in cubic time
- Right angle crossing graphs and 1-planarity
- The straight-line RAC drawing problem is NP-hard
- Zur Struktur 1‐planarer Graphen
- Über 1-optimale Graphen
Cited in
(29)- On fan-crossing and fan-crossing free graphs
- Characterizing and recognizing 4-map graphs
- 1-planarity testing and embedding: an experimental study
- Recognizing and embedding simple optimal 2-planar graphs
- On fan-crossing graphs
- Map graphs having witnesses of large girth
- Fan-crossing free graphs and their relationship to other beyond-planar graphs
- Recognizing outer 1-planar graphs in linear time
- Über 1-optimale Graphen
- A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
- Recognizing IC-planar and NIC-planar graphs
- Beyond planar graphs: introduction
- Quantitative restrictions on crossing patterns
- Algorithms for 1-Planar Graphs
- Edge Partitions and Visibility Representations of 1-planar Graphs
- \(k\)-planar graphs
- Packing trees into 1-planar graphs
- Beyond-planarity: Turán-type results for non-planar bipartite graphs
- On the edge-connectivity and restricted edge-connectivity of optimal 1-planar graphs
- The family of fan-planar graphs
- Optimal 1-planar multigraphs
- On optimal beyond-planar graphs
- Drawing graphs with k vertices per face: complexity and algorithms
- On the complexity of recognizing k^+-real face graphs
- On k-planar graphs without short cycles
- Parameterized algorithms for beyond-planar crossing numbers
- Heuristics for exact 1-planarity testing
- On \(k\)-planar graphs without short cycles
- Heuristics for exact 1-planarity testing
This page was built for publication: Recognizing optimal 1-planar graphs in linear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1702117)
