An annotated bibliography on 1-planarity
arXiv:1703.02261 · doi:10.1016/j.cosrev.2017.06.002
Abstract
The notion of 1-planarity is among the most natural and most studied generalizations of graph planarity. A graph is 1-planar if it has an embedding where each edge is crossed by at most another edge. The study of 1-planar graphs dates back to more than fifty years ago and, recently, it has driven increasing attention in the areas of graph theory, graph algorithms, graph drawing, and computational geometry. This annotated bibliography aims to provide a guiding reference to researchers who want to have an overview of the large body of literature about 1-planar graphs. It reviews the current literature covering various research streams about 1-planarity, such as characterization and recognition, combinatorial properties, and geometric representations. As an additional contribution, we offer a list of open problems on 1-planar graphs.
References in corpus (11)
- Characterisations and Examples of Graph Classes with Bounded Expansion
- Recognizing and Drawing IC-planar Graphs
- Layered Separators in Minor-Closed Graph Classes with Applications
- New bounds on the maximum number of edges in -quasi-planar graphs
- Recognizing Optimal 1-Planar Graphs in Linear Time
- L-Visibility Drawings of IC-planar Graphs
- Simultaneous Visibility Representations of Plane st-graphs Using L-shapes
- Three classes of 1-planar graphs
- Upper bound on the number of edges of an almost planar bipartite graph
- On Partitioning the Edges of 1-Plane Graphs
- Joins of 1-planar graphs
Cited by in corpus (10)
- Planar graphs have bounded queue-number
- A Survey on Graph Drawing Beyond Planarity
- Adjacency Labelling for Planar Graphs (and Beyond)
- Improved product structure for graphs on surfaces
- 1-Fan-Bundle-Planar Drawings of Graphs
- Tree densities in sparse graph classes
- On Visibility Representations of Non-planar Graphs
- Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends
- T-Shape Visibility Representations of 1-Planar Graphs
- A structure of 1-planar graph and its applications to coloring problems