Oswin Aichholzer, Günter Rote, André Schulz, and Birgit Vogtenhuber:

Pointed drawings of planar graphs

  1. In: Proceedings of the 19th Canadian Conference on Computational Geometry, Ottawa, August 20–22, 2007, Editor: Prosenjit Bose, pp. 237–240.
  2. Computational Geometry, Theory and Applications 45 (2012), 482–494 (special issue for the 19th Canadian Conference on Computational Geometry). doi:10.1016/j.comgeo.2010.08.001 (open access)


We study the problem how to draw a planar graph such that every vertex is incident to an angle greater than 180 degrees. In general a straight-line embedding can not guarantee this property. We present algorithms which construct such drawings with either tangent-continuous biarcs or quadratic Bézier curves (parabolic arcs), even if the positions of the vertices are predefined by a given plane straight-line embedding of the graph. Moreover, the graph can be embedded with circular arcs if the vertices can be placed arbitrarily.

  pdf file (gzipped)
other papers about this subject
Last update: March 4, 2008.