Graphs that Admit Right Angle Crossing Drawings
2010
Abstract
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.
Details
Title
Graphs that Admit Right Angle Crossing Drawings
Author(s)
Arikushi, Karin ; Fulek, Radoslav ; Keszegh, Balázs ; Moric, Filip ; Toth, Csaba D.
Published in
Graph Theoretic Concepts in Computer Science - 36th International Workshop
Volume
36
Pages
135-146
Conference
WG 2010
Date
2010
Keywords
Other identifier(s)
View record in Web of Science
Laboratories
DCG
Record Appears in
Scientific production and competences > SB - School of Basic Sciences > SB Archives > DCG - Chair of Combinatorial Geometry
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Conference Papers
Work produced at EPFL
Published
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Conference Papers
Work produced at EPFL
Published
Record creation date
2010-12-30