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$.

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

1 Answer 1


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

  • 2
    $\begingroup$ Thank you for your interest to our topic. Unfortunately, an upper bound for segment number for triangulations does not imply the same upper bound for all planar graphs, because when we add edges to a planar graph making it a triangulation, a priori we can decrease the segment number of the graph, merging the segments in its drawing by the added edges. $\endgroup$ Aug 24, 2019 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.