Straight-line drawings of 1-planar graphs
From MaRDI portal
Publication:6049552
Abstract: A graph is 1-planar if it can be drawn in the plane so that each edge is crossed at most once. However, there are 1-planar graphs which do not admit a straight-line 1-planar drawing. We show that every 1-planar graph has a straight-line drawing with a two-coloring of the edges, so that edges of the same color do not cross. Hence, 1-planar graphs have geometric thickness two. In addition, each edge is crossed by edges with a common vertex if it is crossed more than twice. The drawings use high precision arithmetic with numbers with O(n log n) digits and can be computed in linear time from a 1-planar drawing
Recommendations
Cites work
- \(\mathsf{T}\)-shape visibility representations of 1-planar graphs
- 1-visibility representations of 1-planar graphs
- A first order logic definition of beyond-planar graphs
- A linear-time algorithm for drawing a planar graph on a grid
- A note on 1-planar graphs
- An annotated bibliography on 1-planarity
- Bemerkungen zu einem Sechsfarbenproblem von G. Ringel
- Characterizing and recognizing 4-map graphs
- Convex drawings of 3-connected plane graphs
- Convex Maps
- Convex Representations of Graphs
- Density of straight-line 1-planar graph drawings
- Drawing planar graphs using the canonical ordering
- Drawing plane graphs nicely
- Edge-Disjoint Spanning Trees of Finite Graphs
- Embedding planar graphs in four pages
- Fan-crossing free graphs and their relationship to other beyond-planar graphs
- Fáry's theorem for 1-planar graphs
- Forests, frames, and games: Algorithms for matroid sums and applications
- Four pages are indeed necessary for planar graphs
- Geometric Thickness of Complete Graphs
- Graphs drawn with few crossings per edge
- How to Draw a Graph
- How to draw a planar graph on a grid
- scientific article; zbMATH DE number 432759 (Why is no real title available?)
- scientific article; zbMATH DE number 2123123 (Why is no real title available?)
- scientific article; zbMATH DE number 3885930 (Why is no real title available?)
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- scientific article; zbMATH DE number 3509333 (Why is no real title available?)
- scientific article; zbMATH DE number 1974116 (Why is no real title available?)
- scientific article; zbMATH DE number 3199421 (Why is no real title available?)
- scientific article; zbMATH DE number 3047038 (Why is no real title available?)
- Integer multiplication in time \(O(n\log n)\)
- Multilayer grid embeddings for VLSI
- On fan-crossing and fan-crossing free graphs
- On fan-crossing graphs
- On grids in topological graphs
- On Optimal 2- and 3-Planar Graphs
- On representations of some thickness-two graphs
- On the density of maximal 1-planar graphs
- Planar graphs that need four pages
- Re-embedding a 1-plane graph for a straight-line drawing in linear time
- Recognizing hole-free 4-map graphs in cubic time
- Rectilinear drawings of graphs
- Straight-line grid drawings of 3-connected 1-planar graphs
- Strictly convex drawings of planar graphs
- THE THICKNESS OF AN ARBITRARY COMPLETE GRAPH
- The thickness of graphs: A survey
- Thickness and coarseness of graphs
- Topological graphs with no large grids
- Über 1-optimale Graphen
Cited in
(6)- Density of straight-line 1-planar graph drawings
- Re-embedding a 1-plane graph for a straight-line drawing in linear time
- Straight-line grid drawings of 3-connected 1-planar graphs
- Fáry's theorem for 1-planar graphs
- Geometric thickness of multigraphs is \(\exists \mathbb{R}\)-complete
- 4-connected 1-planar chordal graphs are Hamiltonian-connected
This page was built for publication: Straight-line drawings of 1-planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6049552)
