.png){kind=icon}
.png){kind=icon}
Return
Optimal right angles crossing graphs
.png){kind=icon}
OA
AI
DOI：10.1016/j.comgeo.2026.102255.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A graph is an optimal right angle crossing graph (also called an optimal RAC graph for short) if it has n vertices and 4n-10 edges and admits a straight-line drawing in the plane such that each edge is crossed at most once and edges cross only at a right angle. This implies that the drawing is 3T-or TTX-framed, that is, the outer face is a triangle that is adjacent to three triangles or to two triangles and a crossing. An optimal pseudo-RAC graph is the topological version of an optimal RAC graph, where the restrictions to straight-line edges and right angle crossings are dropped. We show that every 3T-framed optimal pseudo-RAC graph is an optimal RAC graph, that is, 3T-framed optimal pseudo-RAC embeddings can be stretched and orthogonalized. This is not true for TTX-framed embeddings. There are n-vertex 3T-and TTX-framed optimal RAC graphs for every n >= 9, and eleven optimal RAC and fourteen optimal pseudo-RAC graphs with at most eight vertices. Optimal pseudo-RAC graphs can be recognized in O(n3) time, where the recognition algorithm demonstrates that every optimal pseudo-RAC graph has at most three 1-planar embeddings, in which edges are crossed at most once. (c) 2026 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
Keywords:
Topological graphs
Straight-line drawings
Right angle crossing graphs
1-planar graphs
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
0.7
Papers:
14
Citations:
0
Organization
No organization information available