Geodesic
On RAC Drawings of Graphs with Two Bends per Edge
Csaba Tóth1
1 California State University Northridge and Tufts University
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Thirty-first International Symposium on Graph Drawing and Network Visualization, GD 2023 , Tome 28 (2024) no. 2, pp. 37-45.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

It is shown that every $n$-vertex graph that admits a 2-bend RAC drawing in the plane, where the edges are polylines with two bends per edge and any pair of edges can only cross at a right angle, has at most $20n-24$ edges for $n\geq 3$. This improves upon the previous upper bound of $74.2n$; this is the first improvement in more than 12 years. A crucial ingredient of the proof is an upper bound on the size of plane multigraphs with polyline edges in which the first and last segments are either parallel or orthogonal.
DOI : 10.7155/jgaa.v28i2.2939
Keywords: right angle crossing, two-bend drawing, density

Csaba Tóth 1

1 California State University Northridge and Tufts University 
@article{JGAA_2024_28_2_a2,
     author = {Csaba T\'oth},
     title = {On {RAC} {Drawings} of {Graphs} with {Two} {Bends} per {Edge}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {37--45},
     publisher = {mathdoc},
     volume = {28},
     number = {2},
     year = {2024},
     doi = {10.7155/jgaa.v28i2.2939},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2939/}
}
TY  - JOUR
AU  - Csaba Tóth
TI  - On RAC Drawings of Graphs with Two Bends per Edge
JO  - Journal of Graph Algorithms and Applications
PY  - 2024
SP  - 37
EP  - 45
VL  - 28
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2939/
DO  - 10.7155/jgaa.v28i2.2939
LA  - en
ID  - JGAA_2024_28_2_a2
ER  - 
%0 Journal Article
%A Csaba Tóth
%T On RAC Drawings of Graphs with Two Bends per Edge
%J Journal of Graph Algorithms and Applications
%D 2024
%P 37-45
%V 28
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2939/
%R 10.7155/jgaa.v28i2.2939
%G en
%F JGAA_2024_28_2_a2
Csaba Tóth. On RAC Drawings of Graphs with Two Bends per Edge. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Thirty-first International Symposium on Graph Drawing and Network Visualization, GD 2023
					, Tome 28 (2024) no. 2, pp. 37-45. doi : 10.7155/jgaa.v28i2.2939. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2939/

Cité par Sources :