pith. sign in

arxiv: 1808.10470 · v1 · pith:LJ6H3XPMnew · submitted 2018-08-30 · 💻 cs.DS

On RAC Drawings of Graphs with one Bend per Edge

classification 💻 cs.DS
keywords edgesk-bendbenddrawinggraphgraphsboundedge
0
0 comments X
read the original abstract

A k-bend right-angle-crossing drawing or (k-bend RAC drawing}, for short) of a graph is a polyline drawing where each edge has at most k bends and the angles formed at the crossing points of the edges are 90 degrees. Accordingly, a graph that admits a k-bend RAC drawing is referred to as k-bend right-angle-crossing graph (or k-bend RAC, for short). In this paper, we continue the study of the maximum edge-density of 1-bend RAC graphs. We show that an n-vertex 1-bend RAC graph cannot have more than $5.5n-O(1)$ edges. We also demonstrate that there exist infinitely many n-vertex 1-bend RAC graphs with exactly $5n-O(1)$ edges. Our results improve both the previously known best upper bound of $6.5n-O(1)$ edges and the corresponding lower bound of $4.5n-O(\sqrt{n})$ edges by Arikushi et al. (Comput. Geom. 45(4), 169--177 (2012)).

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.