Planarity

A drawing of a graph is called plane if no pair of edges crosses each other. A graph is planar if it admits a plane drawing. This definition of planar graphs is fairly independent of the allowed class of edge visual representations (straight lines, Jordan curves or open polygones).

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.


Planar representation

Consider the situation where a sparse graph is given, and one wants to know if the given node incidence lists form a planar representation and occasionally to generate an according plane drawing. In that case, it does not help to perform a planarity test since the graph might be planar but this particular incidence lists do not form a planar representation. Depending on the application, it might be also unwanted to compute a planar representation from scratch.

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.

[See API]


Planarity recognition and embedding

A planarity test decides whether a graph is planar or not without having a combinatorial embedding, but only an arbitrary order in the node incidence lists. In addition, a plane embedding code reorders the node incidence lists to form a planar representation.

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.

[See API]


Related topics

Return to main page