Graphs that Admit Right Angle Crossing Drawings
2010
Résumé
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.
Détails
Titre
Graphs that Admit Right Angle Crossing Drawings
Auteur(s)
Arikushi, Karin ; Fulek, Radoslav ; Keszegh, Balázs ; Moric, Filip ; Toth, Csaba D.
Publié dans
Graph Theoretic Concepts in Computer Science - 36th International Workshop
Volume
36
Pages
135-146
Présenté à
WG 2010
Date
2010
Mots-clés (libres)
Autres identifiant(s)
Afficher la publication dans Web of Science
Laboratoires
DCG
Le document apparaît dans
Production scientifique et compétences > SB - Faculté des sciences de base > SB Archives > DCG - Chaire de géométrie combinatoire
Production scientifique et compétences > SB - Faculté des sciences de base > Mathématiques
Papiers de conférence
Travail produit à l'EPFL
Publié
Production scientifique et compétences > SB - Faculté des sciences de base > Mathématiques
Papiers de conférence
Travail produit à l'EPFL
Publié
Date de création de la notice
2010-12-30