dual for a planar graph

August 5, 2009 4:15 AM

Can you please draw me the dual of this planar graph.

In case it isn't clear: the little circles are tangential to the vertices of the square and tangential to the big circle. There are only four nodes: the four vertices of the square.

Also: please point me to a generic method of finding a dual for a planar graph if you know of one.

posted by yegga to Science & Nature (3 answers total)

First, find a planar embedding of the graph. (Perhaps you've seen Planarity? Like that.) Since this has only four nodes, you can think of it as being related to K₄, except that each pair of vertex is connected by two edges instead of one, plus there's a loop at each vertex. K₄ is a planar graph, and a planar embedding of that graph is three nodes in a triangle, with the fourth inside that triangle. So give that a try.

Once you have a planar embedding, a dual (not "the dual," since a dual graph is not necessarily unique; which dual you get may depend on which planar embedding you choose, if more than one is possible), place a node in each region of the plane divided by the graph (including the region completely exterior to the graph, then draw edges between any two adjacent regions. Each edge of the original graph should be crossed by exactly one edge of the dual.
posted by DevilsAdvocate at 4:32 AM on August 5, 2009

Here's a picture. The black is a planar embedding of your original graph. The red and green are the vertices and edges, antirespectively, of the dual to that particular embedding.
posted by DevilsAdvocate at 4:51 AM on August 5, 2009

Response by poster: thanks DA!
posted by yegga at 5:59 AM on August 6, 2009