Planarity

check_planarity(G[, counterexample])

Check if a graph is planar and return a counterexample or an embedding.

class PlanarEmbedding(incoming_graph_data=None, **attr)

Represents a planar graph with its planar embedding.

The planar embedding is given by a 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 doubly connected edge lists. 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.

Examples

Create an embedding of a star graph (compare 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()

add_half_edge_ccw(start_node, end_node, reference_neighbor)

Adds a half-edge from start_node to end_node.

The half-edge is added counter clockwise next to the existing half-edge (start_node, reference_neighbor).

Parameters

• start_node (node) – Start node of inserted edge.

• end_node (node) – End node of inserted edge.

• reference_neighbor (node) – End node of reference edge.

Raises

NetworkXException – If the reference_neighbor does not exist.

See also

add_half_edge_cw(), connect_components(), add_half_edge_first()

add_half_edge_cw(start_node, end_node, reference_neighbor)

Adds a half-edge from start_node to end_node.

The half-edge is added clockwise next to the existing half-edge (start_node, reference_neighbor).

Parameters

• start_node (node) – Start node of inserted edge.

• end_node (node) – End node of inserted edge.

• reference_neighbor (node) – End node of reference edge.

Raises

NetworkXException – If the reference_neighbor does not exist.

See also

add_half_edge_ccw(), connect_components(), add_half_edge_first()

add_half_edge_first(start_node, end_node)

The added half-edge is inserted at the first position in the order.

Parameters

• start_node (node)

• end_node (node)

See also

add_half_edge_ccw(), add_half_edge_cw(), connect_components()

check_structure()

Runs without exceptions if this object is valid.

Checks that the following properties are fulfilled:

• Edges go in both directions (because the edge attributes differ).

• Every edge has a ‘cw’ and ‘ccw’ attribute which corresponds to a correct planar embedding.

• A node with a degree larger than 0 has a node attribute ‘first_nbr’.

Running this method verifies that the underlying Graph must be planar.

Raises

NetworkXException – This exception is raised with a short explanation if the PlanarEmbedding is invalid.

connect_components(v, w)

Adds half-edges for (v, w) and (w, v) at some position.

This method should only be called if v and w are in different components, or it might break the embedding. This especially means that if connect_components(v, w) is called it is not allowed to call connect_components(w, v) afterwards. The neighbor orientations in both directions are all set correctly after the first call.

Parameters

• v (node)

• w (node)

See also

add_half_edge_ccw(), add_half_edge_cw(), add_half_edge_first()

get_data()

Converts the adjacency structure into a better readable structure.

Returns

embedding – A dict mapping all nodes to a list of neighbors sorted in clockwise order.

Return type

dict

See also

set_data()

is_directed()

A valid PlanarEmbedding is undirected.

All reverse edges are contained, i.e. for every existing half-edge (v, w) the half-edge in the opposite direction (w, v) is also contained.

neighbors_cw_order(v)

Generator for the neighbors of v in clockwise order.

Parameters

v (node)

Yields

node

next_face_half_edge(v, w)

Returns the following half-edge left of a face.

Parameters

• v (node)

• w (node)

Returns

half-edge

Return type

tuple

set_data(data)

Inserts edges according to given sorted neighbor list.

The input format is the same as the output format of get_data().

Parameters

data (dict) – A dict mapping all nodes to a list of neighbors sorted in clockwise order.

See also

get_data()

traverse_face(v, w, mark_half_edges=None)

Returns nodes on the face that belong to the half-edge (v, w).

The face that is traversed lies to the right of the half-edge (in an orientation where v is below w).

Optionally it is possible to pass a set to which all encountered half edges are added. Before calling this method, this set must not include any half-edges that belong to the face.

Parameters

• v (node) – Start node of half-edge.

• w (node) – End node of half-edge.

• mark_half_edges (set, optional) – Set to which all encountered half-edges are added.

Returns

face – A list of nodes that lie on this face.

Return type

list