6
$\begingroup$

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

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

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 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$
    – Alex Ravsky
    Commented Aug 24, 2019 at 10:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .