# Minimizing the number of segments in drawings of planar graphs

Every planar graph has at most $$3n-6$$ edges, where $$n$$ is the number of vertices. Moreover, every planar graph can be drawn with straight-line edges in the plane, without crossings. For example, for the complete graph $$K_4$$ one actually need 6 segments, so its segment number in 6. For any path its segment number is 1.

Dujmović, Eppstein, Suderman and Wood (2006) have shown that every planar graph can be drawn with at most $$\frac52 n$$ segments (where $$n$$ is the number of vertices).

Can this be improved?

Remark. There are examples of planar graphs that need $$2n\pm O(1)$$ segments.

The problem was asked on 24.03.2019 by Alex Ravsky and Alexander Wolff on pages 94-95 of Volume 2 of the Lviv Scottish Book.

Fig.1 in Dujmović et al. (a) shows a path has segment number $$1$$.

• I took the liberty of adding a figure from the cited paper to illustrate what is meant by "segment number." Aug 23, 2019 at 17:56
• @JosephO'Rourke Very good. Thank you! Aug 23, 2019 at 18:22

Recently, Durocher and Mondal improved the upper bound for plane triangulations to $$7n/3$$: https://doi.org/10.1016/j.comgeo.2018.02.003