On Optimal Beyond-Planar Graphs
Abstract: A graph is beyond-planar if it can be drawn in the plane with a specific restriction on crossings. Several types of beyond-planar graphs have been investigated, such as k-planar graphs where every edge is crossed at most k times and RAC graphs where edges can cross only at a right angle in a straight-line drawing. A graph is optimal if the number of edges coincides with the density for its type. Optimal graphs are special and are known only for some types of beyond-planar graphs, including 1-planar, 2-planar, and RAC graphs. For all types of beyond-planar graphs for which optimal graphs are known, we compute the range for optimal graphs, establish combinatorial properties, and show that every graph is a topological minor of an optimal graph. Note that the minor property is well-known for general beyond-planar graphs. https://www.cgt-journal.org/index.php/cgt/article/view/10
- Standort
-
Deutsche Nationalbibliothek Frankfurt am Main
- Umfang
-
Online-Ressource
- Sprache
-
Englisch
- Erschienen in
-
On Optimal Beyond-Planar Graphs ; volume:2 ; number:1 ; year:2023
Computing in Geometry and Topology ; 2, Heft 1 (2023)
- Urheber
-
Brandenburg, Franz
- DOI
-
10.57717/cgt.v2i1.10
- URN
-
urn:nbn:de:101:1-2023050106041710011936
- Rechteinformation
-
Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
- Letzte Aktualisierung
-
14.08.2025, 11:01 MESZ
Datenpartner
Deutsche Nationalbibliothek. Bei Fragen zum Objekt wenden Sie sich bitte an den Datenpartner.
Beteiligte
- Brandenburg, Franz
Ähnliche Objekte (12)
New Parameters for Beyond-Planar Graphs
Parallel algorithms on planar graphs
Planar Graph Drawing
Harmonic Dirichlet Functions on Planar Graphs
Fixed Parameter Algorithms on Planar Graphs
On Weak Flexibility in Planar Graphs
Multiscale planar graph generation
Discrete complex analysis on planar Quad-graphs
On Upward-Planar L-Drawings of Graphs
On Upward-Planar L-Drawings of Graphs
Hamiltonicity of maximal planar graphs and planar triangulations
Reactive construction of planar overlay graphs on unit disk graphs
New Parameters for Beyond-Planar Graphs
Parallel algorithms on planar graphs
Planar Graph Drawing
Harmonic Dirichlet Functions on Planar Graphs
Fixed Parameter Algorithms on Planar Graphs
On Weak Flexibility in Planar Graphs
Multiscale planar graph generation
Discrete complex analysis on planar Quad-graphs
On Upward-Planar L-Drawings of Graphs
On Upward-Planar L-Drawings of Graphs
Hamiltonicity of maximal planar graphs and planar triangulations
Reactive construction of planar overlay graphs on unit disk graphs
New Parameters for Beyond-Planar Graphs
Parallel algorithms on planar graphs
Planar Graph Drawing
Harmonic Dirichlet Functions on Planar Graphs
Fixed Parameter Algorithms on Planar Graphs
On Weak Flexibility in Planar Graphs
Multiscale planar graph generation
Discrete complex analysis on planar Quad-graphs
On Upward-Planar L-Drawings of Graphs
On Upward-Planar L-Drawings of Graphs
Hamiltonicity of maximal planar graphs and planar triangulations