networkx.algorithms.planarity.PlanarEmbedding

class PlanarEmbedding(incoming_graph_data=None, **attr)

Represents a planar graph with its planar embedding.

The planar embedding is given by a combinatorial embedding.

Note

check_planarity is the preferred way to check if a graph is planar.

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.

See also

is_planar

Preferred way to check if an existing graph is planar.

check_planarity

A convenient way to create a PlanarEmbedding. If not planar, it returns a subgraph that shows this.

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()

__init__(incoming_graph_data=None, **attr)

Initialize a graph with edges, name, or graph attributes.

Parameters:

incoming_graph_datainput graph (optional, default: None)

Data to initialize graph. If None (default) an empty graph is created. The data can be an edge list, or any NetworkX graph object. If the corresponding optional Python packages are installed the data can also be a 2D NumPy array, a SciPy sparse matrix, or a PyGraphviz graph.

attrkeyword arguments, optional (default= no attributes)

Attributes to add to graph as key=value pairs.

See also

convert

Examples

>>> G = nx.Graph()  # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> G = nx.Graph(name="my graph")
>>> e = [(1, 2), (2, 3), (3, 4)]  # list of edges
>>> G = nx.Graph(e)

Arbitrary graph attribute pairs (key=value) may be assigned

>>> G = nx.Graph(e, day="Friday")
>>> G.graph
{'day': 'Friday'}

Methods

add_edge(u_of_edge, v_of_edge, **attr)	Add an edge between u and v.
add_edges_from(ebunch_to_add, **attr)	Add all the edges in ebunch_to_add.
add_half_edge_ccw(start_node, end_node, ...)	Adds a half-edge from start_node to end_node.
add_half_edge_cw(start_node, end_node, ...)	Adds a half-edge from start_node to end_node.
add_half_edge_first(start_node, end_node)	The added half-edge is inserted at the first position in the order.
add_node(node_for_adding, **attr)	Add a single node node_for_adding and update node attributes.
add_nodes_from(nodes_for_adding, **attr)	Add multiple nodes.
add_weighted_edges_from(ebunch_to_add[, weight])	Add weighted edges in ebunch_to_add with specified weight attr
adjacency()	Returns an iterator over (node, adjacency dict) tuples for all nodes.
check_structure()	Runs without exceptions if this object is valid.
clear()	Remove all nodes and edges from the graph.
clear_edges()	Remove all edges from the graph without altering nodes.
connect_components(v, w)	Adds half-edges for (v, w) and (w, v) at some position.
copy([as_view])	Returns a copy of the graph.
edge_subgraph(edges)	Returns the subgraph induced by the specified edges.
get_data()	Converts the adjacency structure into a better readable structure.
get_edge_data(u, v[, default])	Returns the attribute dictionary associated with edge (u, v).
has_edge(u, v)	Returns True if the edge (u, v) is in the graph.
has_node(n)	Returns True if the graph contains the node n.
has_predecessor(u, v)	Returns True if node u has predecessor v.
has_successor(u, v)	Returns True if node u has successor v.
is_directed()	A valid PlanarEmbedding is undirected.
is_multigraph()	Returns True if graph is a multigraph, False otherwise.
nbunch_iter([nbunch])	Returns an iterator over nodes contained in nbunch that are also in the graph.
neighbors(n)	Returns an iterator over successor nodes of n.
neighbors_cw_order(v)	Generator for the neighbors of v in clockwise order.
next_face_half_edge(v, w)	Returns the following half-edge left of a face.
number_of_edges([u, v])	Returns the number of edges between two nodes.
number_of_nodes()	Returns the number of nodes in the graph.
order()	Returns the number of nodes in the graph.
predecessors(n)	Returns an iterator over predecessor nodes of n.
remove_edge(u, v)	Remove the edge between u and v.
remove_edges_from(ebunch)	Remove all edges specified in ebunch.
remove_node(n)	Remove node n.
remove_nodes_from(nodes)	Remove multiple nodes.
reverse([copy])	Returns the reverse of the graph.
set_data(data)	Inserts edges according to given sorted neighbor list.
size([weight])	Returns the number of edges or total of all edge weights.
subgraph(nodes)	Returns a SubGraph view of the subgraph induced on nodes.
successors(n)	Returns an iterator over successor nodes of n.
to_directed([as_view])	Returns a directed representation of the graph.
to_directed_class()	Returns the class to use for empty directed copies.
to_undirected([reciprocal, as_view])	Returns an undirected representation of the digraph.
to_undirected_class()	Returns the class to use for empty undirected copies.
traverse_face(v, w[, mark_half_edges])	Returns nodes on the face that belong to the half-edge (v, w).
update([edges, nodes])	Update the graph using nodes/edges/graphs as input.

Attributes

adj	Graph adjacency object holding the neighbors of each node.
degree	A DegreeView for the Graph as G.degree or G.degree().
edges	An OutEdgeView of the DiGraph as G.edges or G.edges().
in_degree	An InDegreeView for (node, in_degree) or in_degree for single node.
in_edges	An InEdgeView of the Graph as G.in_edges or G.in_edges().
name	String identifier of the graph.
nodes	A NodeView of the Graph as G.nodes or G.nodes().
out_degree	An OutDegreeView for (node, out_degree)
out_edges	An OutEdgeView of the DiGraph as G.edges or G.edges().
pred	Graph adjacency object holding the predecessors of each node.
succ	Graph adjacency object holding the successors of each node.