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

Object Details

• Location: Deutsche Nationalbibliothek Frankfurt am Main
• Extent: Online-Ressource
• Language: Englisch

References and Relationships

• Bibliographic citation: On Optimal Beyond-Planar Graphs ; volume:2 ; number:1 ; year:2023 ; Computing in Geometry and Topology ; 2, Heft 1 (2023)

Contributors, Places and Time

• Creator: Brandenburg, Franz

Further information

• DOI: 10.57717/cgt.v2i1.10
• URN: urn:nbn:de:101:1-2023050106041710011936
• Rights: Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
• Last update: 19.04.20242024, 12:46 AM CEST