TY - JOUR
AU - Brandenburg, Franz
PY - 2023/04/20
Y2 - 2024/11/07
TI - On Optimal Beyond-Planar Graphs
JF - Computing in Geometry and Topology
JA - CompGeomTop
VL - 2
IS - 1
SE - Original Research Articles
DO - 10.57717/cgt.v2i1.10
UR - https://cgt-journal.org/index.php/cgt/article/view/10
SP - 3:1-3:15
AB - <p>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.</p><p>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.</p>
ER -