Graphs that Admit Right Angle Crossing Drawings

We consider right angle crossing (RAC) drawings of graphs in which the edges are represented by polygonal arcs and any two edges can cross only at a right angle. We show that if a graph with n vertices admits a RAC drawing with at most 1 bend or 2 bends per edge, then the number of edges is at most 6.5n and 74.2n, respectively. This is a strengthening of a recent result of Didimo et al. (C) 2011 Elsevier B.V. All rights reserved.


Published in:
Graph Theoretic Concepts in Computer Science - 36th International Workshop, 36, 135-146
Presented at:
WG 2010
Year:
2010
Keywords:
Laboratories:




 Record created 2010-12-30, last modified 2018-09-25


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)