The Minimum Bends in a Polyline Drawing with Fixed Vertex Locations

MaRDI QIDQ6252359zbMATH OpenFDO

Authors Taylor Gordon

Publication date 15 June 2014

Abstract: We consider embeddings of planar graphs in $R^2$ where vertices map to points and edges map to polylines. We refer to such an embedding as a polyline drawing, and ask how few bends are required to form such a drawing for an arbitrary planar graph. It has long been known that even when the vertex locations are completely fixed, a planar graph admits a polyline drawing where edges bend a total of $O(n^2)$ times. Our results show that this number of bends is optimal. In particular, we show that $Omega(n^2)$ total bends is required to form a polyline drawing on any set of fixed vertex locations for almost all planar graphs. This result generalizes all previously known lower bounds, which only applied to convex point sets, and settles 2 open problems.

This page was built for publication: The Minimum Bends in a Polyline Drawing with Fixed Vertex Locations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6252359)