On RAC Drawings of Graphs with Two Bends per Edge

Authors

  • Csaba Tóth California State University Northridge and Tufts University

DOI:

https://doi.org/10.7155/jgaa.v28i2.2939

Keywords:

right angle crossing, two-bend drawing, density

Abstract

It is shown that every $n$-vertex graph that admits a 2-bend RAC drawing in the plane, where the edges are polylines with two bends per edge and any pair of edges can only cross at a right angle, has at most $20n-24$ edges for $n\geq 3$.
This improves upon the previous upper bound of $74.2n$; this is the first improvement in more than 12 years. A crucial ingredient of the proof is an upper bound on the size of plane multigraphs with polyline edges in which the first and last segments are either parallel or orthogonal.

Downloads

Download data is not yet available.

Downloads

Published

2024-06-10

How to Cite

Tóth, C. (2024). On RAC Drawings of Graphs with Two Bends per Edge. Journal of Graph Algorithms and Applications, 28(2), 37–45. https://doi.org/10.7155/jgaa.v28i2.2939