Name
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(root n) edges by Arikushi et al. (Comput. Geom. 45(4), 169-177 (2012)). |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/978-3-030-04414-5_9 | GRAPH DRAWING AND NETWORK VISUALIZATION, GD 2018 |
DocType | Volume | ISSN |
Conference | 11282 | 0302-9743 |
Citations | PageRank | References |
1 | 0.34 | 19 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Patrizio Angelini | 1 | 158 | 25.43 |
| Michael A. Bekos | 2 | 250 | 38.21 |
| Henry Förster | 3 | 3 | 4.40 |
| Michael Kaufmann | 4 | 1224 | 107.33 |