Planar graphs often allow efficient optimization where the general case is hard to solve (e.g. maximum cut). Usually, codes on planar graphs do not use explicit drawings but only the respective clockwise ordering of the node incidence lists. If the incidence lists are ordered as in some plane drawing, this is called a planar representation.
For the described purpose, one calls ExtractEmbedding() which determines the left-hand face indices of all arcs in the plane case. Later on, these indices can be retrieved by abstractMixedGraph::Face(). And arcs with the same face index are on the counter-clockwise boundary of this face in any compliant plane drawing.
Assigning left-hand face indices means to implicitly generate the dual graph.
One of the most famous theorems on graphs states that every non-planar graph has a K_5 or a K_3_3 minor, that are subgraphs obtained by subdividing the edges of a K_5 (a complete graph on five node) or of a K_3_3 (a complete bigraph with three nodes in each part).
While generating the dual graph / the faces is a certificate fora proper planar representation, the mentioned minors allow to verify a negative result of the plane embedding code. Note that only the Hopcroft/Tarjan code can derive such minors, and does only when this is explicitly required.
Return to main page