Crossing Numbers of Beyond-Planar Graphs Revisited
From MaRDI portal
Publication:5084712
Abstract: Graph drawing beyond planarity focuses on drawings of high visual quality for non-planar graphs which are characterized by certain forbidden edge configurations. A natural criterion for the quality of a drawing is the number of edge crossings. The question then arises whether beyond-planar drawings have a significantly larger crossing number than unrestricted drawings. Chimani et al. [GD'19] gave bounds for the ratio between the crossing number of three classes of beyond-planar graphs and the unrestricted crossing number. In this paper we extend their results to the main currently known classes of beyond-planar graphs characterized by forbidden edge configurations and answer several of their open questions.
Recommendations
- Crossing numbers of beyond-planar graphs
- Crossing numbers of beyond-planar graphs
- On the crossing number of almost planar graphs
- On the Crossing Number of Almost Planar Graphs
- Outerplanar crossing numbers of planar graphs
- On graph crossing number and edge planarization
- Crossing and Weighted Crossing Number of Near-Planar Graphs
- On the size of planarly connected crossing graphs
- On the Size of Planarly Connected Crossing Graphs
- The crossing number of 2-planar graphs and its application
Cites work
- Approximating the rectilinear crossing number
- Are crossings important for drawing large graphs?
- Book embeddings and crossing numbers
- Bounds for rectilinear crossing numbers
- Complexity of some geometric and topological problems
- Crossing Number is NP-Complete
- Crossing numbers of beyond-planar graphs
- Crossing numbers of graphs
- Drawing graphs with right angle crossings
- Gap-planar graphs
- New results on rectilinear crossing numbers and plane embeddings
- On the size of planarly connected crossing graphs
- On topological graphs with at most four crossings per edge
- Rectilinear drawings of graphs
- Some provably hard crossing number problems
- Testing gap \(k\)-planarity is NP-complete
- Topological graphs with no large grids
Cited in
(19)- A successful concept for measuring non-planarity of graphs: The crossing number.
- Efficient generation of different topological representations of graphs beyond-planarity
- From crossing-free graphs on wheel sets to embracing simplices and polytopes with few vertices
- On the Size of Planarly Connected Crossing Graphs
- On the Crossing Number of Almost Planar Graphs
- Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor
- Crossing and Weighted Crossing Number of Near-Planar Graphs
- scientific article; zbMATH DE number 1974119 (Why is no real title available?)
- A first order logic definition of beyond-planar graphs
- scientific article; zbMATH DE number 2114110 (Why is no real title available?)
- Beyond planar graphs: introduction
- Beyond-planarity: Turán-type results for non-planar bipartite graphs
- Beyond planar graphs. Communications of National Institute of Informatics (NII) Shonan meetings, Shonan, Japan, November 27 -- December 1, 2016
- Efficient generation of different topological representations of graphs beyond-planarity
- Crossing numbers of beyond-planar graphs
- Crossing numbers of beyond-planar graphs
- On optimal beyond-planar graphs
- Crossing numbers of beyond planar graphs re-revisited: a framework approach
- A unified FPT framework for crossing number problems
This page was built for publication: Crossing Numbers of Beyond-Planar Graphs Revisited
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5084712)
