2010/01/18 by Radoslav Fulek, Fulek, Radoslav, Balázs Keszegh +3
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Handwritten Text Recognition Techniques
paper · pdf · doi:10.48550/arxiv.1001.3117
openalex publication_date 2010/01/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
By a poly-line drawing of a graph G on n vertices we understand a drawing of G in the plane such that each edge is represented by a polygonal arc joining its two respective vertices. We call a turning point of a polygonal arc the bend. We consider the class of graphs that admit a poly-line drawing, in which each edge has at most one bend (resp. two bends) and any two edges can cross only at a right angle. It is shown that the number of edges of such graphs is at most O(n) (resp. O(n log2 n)). This is a strengthening of a recent result of Didimo et al.