For a planar embedding of a planar graph on a plane with straight edges, define a vertex as a sharp vertex if the maximum angle between two consecutive edges around it is more than 180. Or in other words, if there exists a line passing through that vertex in the embedding such that all the edges incident on that vertex lie on one side of the line, then the vertex is sharp otherwise it's not. Also, let us worry only about vertices with degree at least 3.I want to draw planar graphs with few sharp vertices. Has anyone studied such drawings before?In particular, I want to draw planar graphs with max degree 3 such that the number of sharp vertices of degree 3 in the embedding is $O(\log n)$ and the coordinates of the vertices can be written down with a polynomial number of bits.Here's what I can find after spending some time on Google Scholar:My measure of sharpness of a vertex is related to an already studied concept called the Angular Resolution. From Wikipedia:The angular resolution of a drawing of a graph refers to the sharpest angle formed by any two edges that meet at a common vertex of the drawing.Thus a planar drawing with angular resolution $\pi/2$ around degree 3 vertices will be good for my purpose.For a vertex with degree $d$ in the drawing, the angular resolution around it can be at most $2\pi/d$.The question of whether this is tight has been studied in the past, but I can only find asymptotic results. For example, Malitz and Papakostas prove that any planar graph with maximum degree $d$ can be drawn with an angular resolution of $\alpha^d$. But this result doesn't give good bounds for the case when $d=3$.
Drawing graphs with few sharp vertices?
graph theory;cg.comp geom;graph drawing
It is possible to construct 3-regular planar graphs with $\Theta(n)$ biconnected components (see e.g. fig.16 of this paper), each of which must contain at least one sharp vertex.On the other hand, if you require higher levels of connectivity, you can avoid having many sharp vertices. In particular, if you have a 3-connected planar graph, it can be drawn (e.g. by using Steinitz' theorem to find a polyhedral representation and then forming a perspective projection) in such a way that all faces are convex, which causes only the outer face to be sharp. But every 3-connected planar graph can be embedded in such a way that the outer face has at most five vertices (the worst case being a dodecahedron) so you can draw every 3-connected planar graph (3-regular or not) with at most five sharp vertices.