Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I know that any 3-connected simple planar graph with a designated outside face (outer face) has a primal-dual (double) circle packing (Brightwell-Scheinerman Theorem).

Q1- But I am not sure whether we can pin point the location of the vertices of that outside face and then compute the location of the inner circles? Do you now if such a thing is possible or not?

Q2- What if the outside face is a triangle, is it then possible to give three touching circles (possibly with different sizes) in the plane as the circles representing these three vertices and then ask an algorithm to find the location of the other inner vertices?

share|improve this question
I did not understand Q1. As for Q2, I am not so familiar with the double circle packing, so let me talk only about the circle packing. If the graph is a triangulation, then you may choose the sizes of the 3 outer circles to be as you want and the location and sizes of the inner circles are then determined. Since they are determined, the dual circles sizes and locations must also be determined. –  Ori Gurel-Gurevich Oct 20 '12 at 19:54
Thanks very much Ori. About my first question, I should add that it is only different from the second one in that what if we have had more than 3 vertices on the outside face? Is it then possible to choose the size of all the circles on the outside face? –  Hooman Oct 22 '12 at 2:01
If the outside face has more than 3 vertices then you cannot freely choose the radii of their circles. Consider, for example, the graph consisting of a square with a vertex in the center, connected to all 4 corners. Then if you assign radius 1 for three of the corners and 0.01 for the last corner, you'll see that no matter what radius you choose for the center circle, the 2 outer circles adjacent to the small outer circle must overlap. –  Ori Gurel-Gurevich Oct 23 '12 at 5:18
Thanks very much Ori. –  Hooman Oct 23 '12 at 9:58
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.