The planar embedding is given by a :None:None:`combinatorial embedding
<https://en.wikipedia.org/wiki/Graph_embedding#Combinatorial_embedding>`.
Neighbor ordering:
In comparison to a usual graph structure, the embedding also stores the order of all neighbors for every vertex. The order of the neighbors can be given in clockwise (cw) direction or counterclockwise (ccw) direction. This order is stored as edge attributes in the underlying directed graph. For the edge (u, v) the edge attribute 'cw' is set to the neighbor of u that follows immediately after v in clockwise direction.
In order for a PlanarEmbedding to be valid it must fulfill multiple conditions. It is possible to check if these conditions are fulfilled with the method check_structure
. The conditions are:
Edges must go in both directions (because the edge attributes differ)
Every edge must have a 'cw' and 'ccw' attribute which corresponds to a correct planar embedding.
A node with non zero degree must have a node attribute 'first_nbr'.
As long as a PlanarEmbedding is invalid only the following methods should be called:
add_half_edge_ccw
add_half_edge_cw
connect_components
add_half_edge_first
Even though the graph is a subclass of nx.DiGraph, it can still be used for algorithms that require undirected graphs, because the method is_directed
is overridden. This is possible, because a valid PlanarGraph must have edges in both directions.
Half edges:
In methods like add_half_edge_ccw
the term "half-edge" is used, which is a term that is used in :None:None:`doubly connected edge lists
<https://en.wikipedia.org/wiki/Doubly_connected_edge_list>`. It is used to emphasize that the edge is only in one direction and there exists another half-edge in the opposite direction. While conventional edges always have two faces (including outer face) next to them, it is possible to assign each half-edge exactly one face. For a half-edge (u, v) that is orientated such that u is below v then the face that belongs to (u, v) is to the right of this half-edge.
Represents a planar graph with its planar embedding.
check_planarity
A convenient way to create a :None:None:`PlanarEmbedding`. If not planar, it returns a subgraph that shows this.
is_planar
Preferred way to check if an existing graph is planar.
Create an embedding of a star graph (compare :None:None:`nx.star_graph(3)`):
>>> G = nx.PlanarEmbedding()
... G.add_half_edge_cw(0, 1, None)
... G.add_half_edge_cw(0, 2, 1)
... G.add_half_edge_cw(0, 3, 2)
... G.add_half_edge_cw(1, 0, None)
... G.add_half_edge_cw(2, 0, None)
... G.add_half_edge_cw(3, 0, None)
Alternatively the same embedding can also be defined in counterclockwise orientation. The following results in exactly the same PlanarEmbedding:
>>> G = nx.PlanarEmbedding()
... G.add_half_edge_ccw(0, 1, None)
... G.add_half_edge_ccw(0, 3, 1)
... G.add_half_edge_ccw(0, 2, 3)
... G.add_half_edge_ccw(1, 0, None)
... G.add_half_edge_ccw(2, 0, None)
... G.add_half_edge_ccw(3, 0, None)
After creating a graph, it is possible to validate that the PlanarEmbedding object is correct:
>>> G.check_structure()See :
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.algorithms.planarity.check_planarity
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them