15
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Not sure what this means. If you draw any regular convex polygon, the max angle around it is more than 180. And a regular convex polygon with large n is pretty far from "sharp". $\endgroup$
    – Suresh Venkat
    May 1, 2012 at 20:24
  • $\begingroup$ I am defining sharpness as a property of a vertex, not the entire drawing. So if for a vertex, a straight line can be drawn such that all edges incident on that vertex lie on one side of the straight line, then the vertex is "sharp" otherwise it's not. Hmm, may be I should write this in the original question. $\endgroup$
    – Vinayak Pathak
    May 1, 2012 at 20:38
  • $\begingroup$ @Vinayak: what about vertices with degree 1 and 2? $\endgroup$
    – Marzio De Biasi
    May 1, 2012 at 20:52
  • $\begingroup$ They can be ignored. $\endgroup$
    – Vinayak Pathak
    May 1, 2012 at 20:57
  • $\begingroup$ If angular resolution is what you want, that makes sense because that's looking at the MINIMUM angle between adjacent edges. that's quite different to what you defined before. $\endgroup$
    – Suresh Venkat
    May 2, 2012 at 3:49

1 Answer 1

Reset to default
13
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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