2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – Ori Gurel-Gurevich
    Commented Oct 20, 2012 at 19:54
  • $\begingroup$ 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? $\endgroup$
    – Hooman
    Commented Oct 22, 2012 at 2:01
  • $\begingroup$ 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. $\endgroup$
    – Ori Gurel-Gurevich
    Commented Oct 23, 2012 at 5:18

0

Reset to default

You must log in to answer this question.