dual for a planar graph
August 5, 2009 4:15 AM   Subscribe

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 K4, except that each pair of vertex is connected by two edges instead of one, plus there's a loop at each vertex. K4 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

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

« Older To erase or not to erase, that is the bookworm's...   |   Making pate palatable Newer »
This thread is closed to new comments.