Repository: networkx/networkx

Issue:
Modifying the edges of a PlannarEmbedding graph invalidates its structure.
<!-- If you have a general question about NetworkX, please use the discussions tab to create a new discussion -->

<!--- Provide a general summary of the issue in the Title above -->

If an edge is removed and another one added to a `PlanarEmbedding`, it becomes invalid even if the modifications result in a planar embedding (see notebook below).

### Current Behavior

An error is produced upon calling `PlanarEmbedding.check_structure()`.

### Expected Behavior

No error (provided the graph is still a planar embedding).

### Steps to Reproduce

```python
import networkx as nx

edges = ((0, 1), (1, 2), (2, 3), (3, 0), (0, 2))
pos = ((0, 0), (1, 0), (1, 1), (0, 1))

Gmwe = nx.Graph(((0, 1),
                 (1, 2),
                 (2, 3),
                 (3, 0),
                 (0, 2)))

cert, Pmwe = nx.check_planarity(Gmwe)
cert
```
Output:
    True

```python
type(Pmwe)
```
Output:
    networkx.algorithms.planarity.PlanarEmbedding

```python
nx.draw(Pmwe, with_labels=True, pos=pos)
```
![output_5_0](https://github.com/networkx/networkx/assets/856825/ea8589c7-6d20-46f3-bb12-2d8641f28bdf)
```python
list(Pmwe.neighbors_cw_order(0))
```
Output:
    [1, 3, 2]
```python
list(Pmwe.neighbors_cw_order(2))
```
Output:
    [1, 0, 3]

Now we remove the edge `(0, 2)` and add `(3, 1)`, inserting each half-edge in the proper position.
```python
Pmwe.remove_edges_from(((0, 2), (2, 0)))
Pmwe.add_half_edge_ccw(1, 3, 2)
Pmwe.add_half_edge_cw(3, 1, 2)
```

```python
nx.draw(Pmwe, with_labels=True, pos=pos)
```
![output_10_0](https://github.com/networkx/networkx/assets/856825/20adc934-4c37-46bf-a433-c786bf8b3cca)

Why is the modified PlanarEmbedding not structurally sound anymore?

```python
Pmwe.check_structure()
```
Output:

    ---------------------------------------------------------------------------

    KeyError                                  Traceback (most recent call last)

    File ~\programs\miniconda\envs\interarray\lib\site-packages\networkx\algorithms\planarity.py:938, in PlanarEmbedding.check_structure(self)
        937 try:
    --> 938     sorted_nbrs = set(self.neighbors_cw_order(v))
        939 except KeyError as err:
    

    File ~\programs\miniconda\envs\interarray\lib\site-packages\networkx\algorithms\planarity.py:915, in PlanarEmbedding.neighbors_cw_order(self, v)
        914 yield current_node
    --> 915 current_node = self[v][current_node]["cw"]
    

    File ~\programs\miniconda\envs\interarray\lib\site-packages\networkx\classes\coreviews.py:53, in AtlasView.__getitem__(self, key)
         52 def __getitem__(self, key):
    ---> 53     return self._atlas[key]
    

    KeyError: 2

    
    The above exception was the direct cause of the following exception:
    

    NetworkXException                         Traceback (most recent call last)

    Cell In[12], line 1
    ----> 1 Pmwe.check_structure()
    

    File ~\programs\miniconda\envs\interarray\lib\site-packages\networkx\algorithms\planarity.py:941, in PlanarEmbedding.check_structure(self)
        939 except KeyError as err:
        940     msg = f"Bad embedding. Missing orientation for a neighbor of {v}"
    --> 941     raise nx.NetworkXException(msg) from err
        943 unsorted_nbrs = set(self[v])
        944 if sorted_nbrs != unsorted_nbrs:
    

    NetworkXException: Bad embedding. Missing orientation for a neighbor of 0


The `check_planarity()` function has no problems with it:

```python
cert, Nmwe = nx.check_planarity(Pmwe)
cert
```
Output:
    True

```python
nx.draw(Nmwe, with_labels=True, pos=pos)
```
![output_15_0](https://github.com/networkx/networkx/assets/856825/a7bfc515-0bd7-4c47-a158-543af6203f63)
 
```python
nx.difference(Pmwe, Nmwe).edges
```
Output:
    OutEdgeView([])


### Environment

Python version: 3.10.12
NetworkX version: 3.1

### Additional context

<!--- Add any other context about the problem here, screenshots, etc. -->


Discussion:
mdealencar: Is that test what you had in mind?
dschult: Thanks for that.  It should go in the tests folder next to the `planarity.py` module.  So, in this case, `networkx/algorithms/tests/test_planarity.py` sorry for not being clear.

I also now realize that this creates a difference in the treatment of `add_edge` and `remove_edge`.  In the current code, `add_edge` and `remove_edge` are both handled by the superclass `nx.DiGraph`.  Adding half edges is handled by the subclass `PlanarEmbedding`.  Since this is removing half edges should we create new methods instead of these -- something like:  `remove_half_edge_cw` and `remove_half_edge_ccw`?

Another question:  what happens if removing that edge makes it no longer possible to have a planar graph?

Yes another question:  what about removing nodes?  Is that not needed?  

As an aside, I think these features were not included because they led to headaches -- and a user could recreate the graph with the removed edges if needed. But that was obviously not documented nor enforced.  
What should the api be here?
rossbar: > As an aside, I think these features were not included because they led to headaches -- and a user could recreate the graph with the removed edges if needed. But that was obviously not documented nor enforced.

Perhaps the `PlanarEmbedding` could be made immutable, at least for adding/removing nodes/edges (attributes should still be okay, right?). If a user wants to modify the embedding, they can create a graph object from the embedding, e.g. `H = nx.Graph(my_embedding)`. It puts more burden on the user in terms of LOC, but at least that way things are explicit - planarity is no longer implied by the type of the object, and the need to re-compute planarity after a change is clear.
mdealencar: > Perhaps the `PlanarEmbedding` could be made immutable, at least for adding/removing nodes/edges (attributes should still be okay, right?). If a user wants to modify the embedding, they can create a graph object from the embedding, e.g. `H = nx.Graph(my_embedding)`. It puts more burden on the user in terms of LOC, but at least that way things are explicit - planarity is no longer implied by the type of the object, and the need to re-compute planarity after a change is clear.

I would rather not have `PlanarEmbedding` immutable. AFAIK, removing edges or nodes from a planar embedding cannot make it not a planar embedding. As long as the structures' internal references are updated correctly, the graph should pass the `PlanarEmbedding.check_structure()`.

I added a `.remove_node()` method and modified the `.remove_edge()` to also update the `first_nbr` node property, which I had overlooked earlier.

That way, only the addition of edges can lead to invalidating the embedding. If there is a need to make `PlanarEmbedding` more robust to changes in the graph, I'd suggest replacing the `add_half_edge...()` methods by a single `add_edge()` that checks locally if planarity is preserved.
dschult: I'm afraid there is a lot more checking to do before this PR will be merged.
For example, you stated that removing edges does not break the trait of the graph being planar. I agree... :}
But it might break the representation that `PlanarEmbedding` provides to check that a graph is planar. For example, the code says that one must be careful not to call the method to connect components if the components are already connected, especially if one half edge already exists and you are adding the other half edge. So, what does that imply about breaking a component into two components?  Is it enough to check local traits?

You can tell from comments in the code that it was written in a fragile way. As long as you do "normal" things, it will be correct. But it doesn't protect you from yourself. Another example if that it subclasses `nx.DiGraph` but changes `G.is_directed()` to return False.  That will break lots of code in NetworkX if you try to use it as a networkx graph. This fragility impacts us as maintainers because we have to figure out the impact of seemingly small changes. 

Another example is that adding an edge to the graph could easily make it no longer planar. But we have no mechanism for tracking that. This PR will provide `G.remove_edge` but not make `G.add_edge` correct (nor block it from happening). Users will be more tempted to use `G.add_edge` if they are using `G.remove_edge` somewhere else.

It'd be great to expand on this class to make it editable -- with checks for each edit to ensure that the attribute structure is maintained. Or make the class "frozen" as suggested above. Then people are expected to change the graph in its form as a standard networkx graph. Once changed they can go back to a planar embedding to check traits there.  Both would help this code become less "fragile". But the `is_directed` feature will still make it hard to use/maintain.

Can you convince us that this change does not break the PlanarEmbedding data structure? Are you willing to take on making the class fully editable?  Can you describe a use case where making these changes to the code and maintaining them is better for the users than having them use the networkx graph to make graph changes and then convert the new graph to a PlanarEmbedding to check planarity. How slow is that anyway? 

I think those are three things I would want to see for this.
mdealencar: >  But it might break the representation that `PlanarEmbedding` provides to check that a graph is planar.

The representation `planarity_state = LRPlanarity(G)` only exists within a `check_planarity(G)` call (i.e. outside the PlanarEmbedding class).

The only structure beyond a DiGraph that a PlanarEmbedding contains is encoded in edge attributes `('cw', 'ccw')` and node attribute `'first_nbr'`. [PlanarEmbedding.check_structure(self)](https://github.com/networkx/networkx/blob/f93f0e2a066fc456aa447853af9d00eec1058542/networkx/algorithms/planarity.py#L940) checks the consistency of these attributes plus some global checks based on DiGraph properties only (e.g. both half-edges present, Eulers' formula). This check is distributive over all connected components of the graph (fresh call to `nx.connected_components(self)` each time), which also clears this:

> So, what does that imply about breaking a component into two components? Is it enough to check local traits?

There is no need to worry about the splitting of a component by an edge removal: the planarity code is prepared to deal with multiple components.

> Another example is that adding an edge to the graph could easily make it no longer planar. But we have no mechanism for tracking that. This PR will provide `G.remove_edge` but not make `G.add_edge` correct (nor block it from happening). Users will be more tempted to use `G.add_edge` if they are using `G.remove_edge` somewhere else.

I can include the blocking of `PlanarEmbedding.add_edge()`. Any hints on which exception to throw?

> Another example if that it subclasses `nx.DiGraph` but changes `G.is_directed()` to return False. That will break lots of code in NetworkX if you try to use it as a networkx graph. This fragility impacts us as maintainers because we have to figure out the impact of seemingly small changes.

I have the impression that implementing PlanarEmbedding as a nx.Graph would be less of a hassle, but I haven't looked deep enough into all the details. Any valid embedding will have both edges anyway. It would just be a matter of keying `('cw', 'ccw')` by source node. The only advantage I see of using  DiGraph is that the algorithm for building it can add all half-edges from a node at a time, before dealing with the corresponding complementary half-edges.

> It'd be great to expand on this class to make it editable -- with checks for each edit to ensure that the attribute structure is maintained.

I'm proposing making it editable only for removals. I believe the PR enables removals in a non-breaking way, which is an improvement over the current status. For additions, it would require implementing a local planarity test (I can take a shot at it, but I am not sure how complicated that is). For the time being, additions would throw an exception.

> Can you convince us that this change does not break the PlanarEmbedding data structure?

I hope the above was convincing enough.

> Are you willing to take on making the class fully editable?

I'd have to investigate a bit further for that (and whether the use of nx.Graph would be an improvement).

> Can you describe a use case where making these changes to the code and maintaining them is better for the users than having them use the networkx graph to make graph changes and then convert the new graph to a PlanarEmbedding to check planarity.

I cannot say what is better for the users, but I'm using my PR in a [project](https://github.com/mdealencar/interarray) and find it useful. I even add edges (which I know that will maintain the planarity). I'm working with Euclidean Delaunay triangulations, but I need to make small adjustments to them as a spanning tree is built over the nodes. It would impact negatively my algorithm if I were to recreate a PlanarEmbedding after each change.

The current state is buggy, so I think this PR is an improvement, but I agree those changes add to the maintenance burden.

> How slow is that anyway?

Not sure, but it's not a trivial procedure.
dschult: We talked about this in a community meeting recently and we are OK with having remove_edge/node added to the class, but we'd really like it if the other morphing methods would raise exceptions. We are worried that people will see that they can remove and edge and then try to add an edge. 

Could you add methods for the following that simply raise an exception stating that this is not allowed for a PlanarEmbedding?  The methods are (obtained from the function [frozen](https://networkx.org/documentation/stable/_modules/networkx/classes/function.html#freeze) which turns off all of these).
```
    G.add_node
    G.add_nodes_from
    G.add_edge
    G.add_edges_from
    G.add_weighted_edges_from
 ```
If that's too much for now let us know and we'll find a way to get it in.
mdealencar: > Could you add methods for the following that simply raise an exception stating that this is not allowed for a PlanarEmbedding?
> 
>     G.add_edge
>     G.add_edges_from
>     G.add_weighted_edges_from
I had to override those above by overriding the base class' `__init__()`, since they are necessary if the instance is created with `incoming_graph_data` (tests do that a lot).

As for these:
>     G.add_node
>     G.add_nodes_from
Addition of nodes do not pose a risk of invalidating the PlanarEmbedding and are required by `LRPlanarity.lr_planarity()` in order to create a PlanarEmbedding by calling `check_planarity(nx.Graph())`. So I didn't touch them.

Let me know if there is anything missing.

Patch:
diff --git a/networkx/algorithms/planarity.py b/networkx/algorithms/planarity.py
index c5611eca3..59206b412 100644
--- a/networkx/algorithms/planarity.py
+++ b/networkx/algorithms/planarity.py
@@ -855,6 +855,22 @@ class PlanarEmbedding(nx.DiGraph):
 
     """
 
+    def __init__(self, incoming_graph_data=None, **attr):
+        super().__init__(incoming_graph_data=incoming_graph_data, **attr)
+        self.add_edge = self.__forbidden
+        self.add_edges_from = self.__forbidden
+        self.add_weighted_edges_from = self.__forbidden
+
+    def __forbidden(self, *args, **kwargs):
+        """Forbidden operation
+
+        Any edge additions to a PlanarEmbedding should be done using
+        method `add_half_edge`.
+        """
+        raise NotImplementedError(
+            "Use `add_half_edge` method to add edges to a PlanarEmbedding."
+        )
+
     def get_data(self):
         """Converts the adjacency structure into a better readable structure.
 
@@ -896,6 +912,75 @@ class PlanarEmbedding(nx.DiGraph):
                 self.add_half_edge(v, w, cw=ref)
                 ref = w
 
+    def remove_node(self, n):
+        """Remove node n.
+
+        Removes the node n and all adjacent edges, updating the
+        PlanarEmbedding to account for any resulting edge removal.
+        Attempting to remove a non-existent node will raise an exception.
+
+        Parameters
+        ----------
+        n : node
+           A node in the graph
+
+        Raises
+        ------
+        NetworkXError
+           If n is not in the graph.
+
+        See Also
+        --------
+        remove_nodes_from
+
+        """
+        try:
+            for u in self._pred[n]:
+                succs_u = self._succ[u]
+                un_cw = succs_u[n]["cw"]
+                un_ccw = succs_u[n]["ccw"]
+                del succs_u[n]
+                del self._pred[u][n]
+                if n != un_cw:
+                    succs_u[un_cw]["ccw"] = un_ccw
+                    succs_u[un_ccw]["cw"] = un_cw
+            del self._node[n]
+            del self._succ[n]
+            del self._pred[n]
+        except KeyError as err:  # NetworkXError if n not in self
+            raise nx.NetworkXError(
+                f"The node {n} is not in the planar embedding."
+            ) from err
+
+    def remove_nodes_from(self, nodes):
+        """Remove multiple nodes.
+
+        Parameters
+        ----------
+        nodes : iterable container
+            A container of nodes (list, dict, set, etc.).  If a node
+            in the container is not in the graph it is silently ignored.
+
+        See Also
+        --------
+        remove_node
+
+        Notes
+        -----
+        When removing nodes from an iterator over the graph you are changing,
+        a `RuntimeError` will be raised with message:
+        `RuntimeError: dictionary changed size during iteration`. This
+        happens when the graph's underlying dictionary is modified during
+        iteration. To avoid this error, evaluate the iterator into a separate
+        object, e.g. by using `list(iterator_of_nodes)`, and pass this
+        object to `G.remove_nodes_from`.
+
+        """
+        for n in nodes:
+            if n in self._node:
+                self.remove_node(n)
+            # silently skip non-existing nodes
+
     def neighbors_cw_order(self, v):
         """Generator for the neighbors of v in clockwise order.
 
@@ -940,6 +1025,7 @@ class PlanarEmbedding(nx.DiGraph):
             End node of reference edge.
             Omit or pass `None` if adding the first out-half-edge of `start_node`.
 
+
         Raises
         ------
         NetworkXException
@@ -962,7 +1048,7 @@ class PlanarEmbedding(nx.DiGraph):
                 if ccw is not None:
                     raise nx.NetworkXError("Only one of cw/ccw can be specified.")
                 ref_ccw = succs[cw]["ccw"]
-                self.add_edge(start_node, end_node, cw=cw, ccw=ref_ccw)
+                super().add_edge(start_node, end_node, cw=cw, ccw=ref_ccw)
                 succs[ref_ccw]["cw"] = end_node
                 succs[cw]["ccw"] = end_node
                 # when (cw == leftmost_nbr), the newly added neighbor is
@@ -973,7 +1059,7 @@ class PlanarEmbedding(nx.DiGraph):
                 if ccw not in succs:
                     raise nx.NetworkXError("Invalid counterclockwise reference node.")
                 ref_cw = succs[ccw]["cw"]
-                self.add_edge(start_node, end_node, cw=ref_cw, ccw=ccw)
+                super().add_edge(start_node, end_node, cw=ref_cw, ccw=ccw)
                 succs[ref_cw]["ccw"] = end_node
                 succs[ccw]["cw"] = end_node
                 move_leftmost_nbr_to_end = True
@@ -986,11 +1072,12 @@ class PlanarEmbedding(nx.DiGraph):
                 # we keep track of the leftmost neighbor, which we accomplish
                 # by keeping it as the last key in dict self._succ[start_node]
                 succs[leftmost_nbr] = succs.pop(leftmost_nbr)
+
         else:
             if cw is not None or ccw is not None:
                 raise nx.NetworkXError("Invalid reference node.")
             # adding the first edge out of start_node
-            self.add_edge(start_node, end_node, ccw=end_node, cw=end_node)
+            super().add_edge(start_node, end_node, ccw=end_node, cw=end_node)
 
     def check_structure(self):
         """Runs without exceptions if this object is valid.
@@ -1107,6 +1194,79 @@ class PlanarEmbedding(nx.DiGraph):
         """
         self.add_half_edge(start_node, end_node, ccw=reference_neighbor)
 
+    def remove_edge(self, u, v):
+        """Remove the edge between u and v.
+
+        Parameters
+        ----------
+        u, v : nodes
+        Remove the half-edges (u, v) and (v, u) and update the
+        edge ordering around the removed edge.
+
+        Raises
+        ------
+        NetworkXError
+        If there is not an edge between u and v.
+
+        See Also
+        --------
+        remove_edges_from : remove a collection of edges
+        """
+        try:
+            succs_u = self._succ[u]
+            succs_v = self._succ[v]
+            uv_cw = succs_u[v]["cw"]
+            uv_ccw = succs_u[v]["ccw"]
+            vu_cw = succs_v[u]["cw"]
+            vu_ccw = succs_v[u]["ccw"]
+            del succs_u[v]
+            del self._pred[v][u]
+            del succs_v[u]
+            del self._pred[u][v]
+            if v != uv_cw:
+                succs_u[uv_cw]["ccw"] = uv_ccw
+                succs_u[uv_ccw]["cw"] = uv_cw
+            if u != vu_cw:
+                succs_v[vu_cw]["ccw"] = vu_ccw
+                succs_v[vu_ccw]["cw"] = vu_cw
+        except KeyError as err:
+            raise nx.NetworkXError(
+                f"The edge {u}-{v} is not in the planar embedding."
+            ) from err
+
+    def remove_edges_from(self, ebunch):
+        """Remove all edges specified in ebunch.
+
+        Parameters
+        ----------
+        ebunch: list or container of edge tuples
+            Each pair of half-edges between the nodes given in the tuples
+            will be removed from the graph. The nodes can be passed as:
+
+                - 2-tuples (u, v) half-edges (u, v) and (v, u).
+                - 3-tuples (u, v, k) where k is ignored.
+
+        See Also
+        --------
+        remove_edge : remove a single edge
+
+        Notes
+        -----
+        Will fail silently if an edge in ebunch is not in the graph.
+
+        Examples
+        --------
+        >>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
+        >>> ebunch = [(1, 2), (2, 3)]
+        >>> G.remove_edges_from(ebunch)
+        """
+        for e in ebunch:
+            u, v = e[:2]  # ignore edge data
+            # assuming that the PlanarEmbedding is valid, if the half_edge
+            # (u, v) is in the graph, then so is half_edge (v, u)
+            if u in self._succ and v in self._succ[u]:
+                self.remove_edge(u, v)
+
     def connect_components(self, v, w):
         """Adds half-edges for (v, w) and (w, v) at some position.
 
diff --git a/networkx/algorithms/similarity.py b/networkx/algorithms/similarity.py
index 3a1cfff81..183b41f66 100644
--- a/networkx/algorithms/similarity.py
+++ b/networkx/algorithms/similarity.py
@@ -322,7 +322,8 @@ def optimal_edit_paths(
         edge_edit_path : list of tuples ((u1, v1), (u2, v2))
 
     cost : numeric
-        Optimal edit path cost (graph edit distance).
+        Optimal edit path cost (graph edit distance). When the cost
+        is zero, it indicates that `G1` and `G2` are isomorphic.
 
     Examples
     --------
@@ -334,6 +335,14 @@ def optimal_edit_paths(
     >>> cost
     5.0
 
+    Notes
+    -----
+    To transform `G1` into a graph isomorphic to `G2`, apply the node
+    and edge edits in the returned ``edit_paths``.
+    In the case of isomorphic graphs, the cost is zero, and the paths
+    represent different isomorphic mappings (isomorphisms). That is, the
+    edits involve renaming nodes and edges to match the structure of `G2`.
+
     See Also
     --------
     graph_edit_distance, optimize_edit_paths
diff --git a/networkx/algorithms/tree/mst.py b/networkx/algorithms/tree/mst.py
index f4cec03dc..ee264d41a 100644
--- a/networkx/algorithms/tree/mst.py
+++ b/networkx/algorithms/tree/mst.py
@@ -897,14 +897,15 @@ def random_spanning_tree(G, weight=None, *, multiplicative=True, seed=None):
             #    itself.
             if G.number_of_edges() == 1:
                 return G.edges(data=weight).__iter__().__next__()[2]
-            # 2. There are more than two edges in the graph. Then, we can find the
+            # 2. There are no edges or two or more edges in the graph. Then, we find the
             #    total weight of the spanning trees using the formula in the
-            #    reference paper: take the weight of that edge and multiple it by
-            #    the number of spanning trees which have to include that edge. This
+            #    reference paper: take the weight of each edge and multiply it by
+            #    the number of spanning trees which include that edge. This
             #    can be accomplished by contracting the edge and finding the
             #    multiplicative total spanning tree weight if the weight of each edge
             #    is assumed to be 1, which is conveniently built into networkx already,
-            #    by calling total_spanning_tree_weight with weight=None
+            #    by calling total_spanning_tree_weight with weight=None.
+            #    Note that with no edges the returned value is just zero.
             else:
                 total = 0
                 for u, v, w in G.edges(data=weight):
@@ -913,6 +914,10 @@ def random_spanning_tree(G, weight=None, *, multiplicative=True, seed=None):
                     )
                 return total
 
+    if G.number_of_nodes() < 2:
+        # no edges in the spanning tree
+        return nx.empty_graph(G.nodes)
+
     U = set()
     st_cached_value = 0
     V = set(G.edges())


Test patch:
diff --git a/networkx/algorithms/tests/test_planarity.py b/networkx/algorithms/tests/test_planarity.py
index 02b1d32a9..99bcff418 100644
--- a/networkx/algorithms/tests/test_planarity.py
+++ b/networkx/algorithms/tests/test_planarity.py
@@ -277,6 +277,20 @@ class TestLRPlanarity:
             G.add_node(1)
             get_counterexample_recursive(G)
 
+    def test_edge_removal_from_planar_embedding(self):
+        # PlanarEmbedding.check_structure() must succeed after edge removal
+        edges = ((0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (0, 2), (0, 3))
+        G = nx.Graph(edges)
+        cert, P = nx.check_planarity(G)
+        assert cert is True
+        P.remove_edge(0, 2)
+        self.check_graph(P, is_planar=True)
+        P.add_half_edge_ccw(1, 3, 2)
+        P.add_half_edge_cw(3, 1, 2)
+        self.check_graph(P, is_planar=True)
+        P.remove_edges_from(((0, 3), (1, 3)))
+        self.check_graph(P, is_planar=True)
+
 
 def check_embedding(G, embedding):
     """Raises an exception if the combinatorial embedding is not correct
@@ -410,19 +424,51 @@ class TestPlanarEmbeddingClass:
         data_cmp = {0: [3, 2, 1], 1: [0], 2: [0], 3: [0]}
         assert data == data_cmp
 
-    def test_missing_edge_orientation(self):
+    def test_edge_removal(self):
         embedding = nx.PlanarEmbedding()
-        embedding.add_edge(1, 2)
-        embedding.add_edge(2, 1)
+        embedding.set_data(
+            {
+                1: [2, 5, 7],
+                2: [1, 3, 4, 5],
+                3: [2, 4],
+                4: [3, 6, 5, 2],
+                5: [7, 1, 2, 4],
+                6: [4, 7],
+                7: [6, 1, 5],
+            }
+        )
+        # remove_edges_from() calls remove_edge(), so both are tested here
+        embedding.remove_edges_from(((5, 4), (1, 5)))
+        embedding.check_structure()
+        embedding_expected = nx.PlanarEmbedding()
+        embedding_expected.set_data(
+            {
+                1: [2, 7],
+                2: [1, 3, 4, 5],
+                3: [2, 4],
+                4: [3, 6, 2],
+                5: [7, 2],
+                6: [4, 7],
+                7: [6, 1, 5],
+            }
+        )
+        assert nx.utils.graphs_equal(embedding, embedding_expected)
+
+    def test_missing_edge_orientation(self):
+        embedding = nx.PlanarEmbedding({1: {2: {}}, 2: {1: {}}})
         with pytest.raises(nx.NetworkXException):
             # Invalid structure because the orientation of the edge was not set
             embedding.check_structure()
 
     def test_invalid_edge_orientation(self):
-        embedding = nx.PlanarEmbedding()
-        embedding.add_half_edge(1, 2)
-        embedding.add_half_edge(2, 1)
-        embedding.add_edge(1, 3)
+        embedding = nx.PlanarEmbedding(
+            {
+                1: {2: {"cw": 2, "ccw": 2}},
+                2: {1: {"cw": 1, "ccw": 1}},
+                1: {3: {}},
+                3: {1: {}},
+            }
+        )
         with pytest.raises(nx.NetworkXException):
             embedding.check_structure()
 
@@ -461,12 +507,23 @@ class TestPlanarEmbeddingClass:
         assert face == [1, 2]
 
     def test_unsuccessful_face_traversal(self):
-        embedding = nx.PlanarEmbedding()
-        embedding.add_edge(1, 2, ccw=2, cw=3)
-        embedding.add_edge(2, 1, ccw=1, cw=3)
+        embedding = nx.PlanarEmbedding(
+            {1: {2: {"cw": 3, "ccw": 2}}, 2: {1: {"cw": 3, "ccw": 1}}}
+        )
         with pytest.raises(nx.NetworkXException):
             embedding.traverse_face(1, 2)
 
+    def test_forbidden_methods(self):
+        embedding = nx.PlanarEmbedding()
+        embedding.add_node(42)  # no exception
+        embedding.add_nodes_from([(23, 24)])  # no exception
+        with pytest.raises(NotImplementedError):
+            embedding.add_edge(1, 3)
+        with pytest.raises(NotImplementedError):
+            embedding.add_edges_from([(0, 2), (1, 4)])
+        with pytest.raises(NotImplementedError):
+            embedding.add_weighted_edges_from([(0, 2, 350), (1, 4, 125)])
+
     @staticmethod
     def get_star_embedding(n):
         embedding = nx.PlanarEmbedding()
diff --git a/networkx/algorithms/tree/tests/test_mst.py b/networkx/algorithms/tree/tests/test_mst.py
index 373f16cf7..bc55000a6 100644
--- a/networkx/algorithms/tree/tests/test_mst.py
+++ b/networkx/algorithms/tree/tests/test_mst.py
@@ -706,3 +706,27 @@ def test_random_spanning_tree_additive_large():
     # Assert that p is greater than the significance level so that we do not
     # reject the null hypothesis
     assert not p < 0.05
+
+
+def test_random_spanning_tree_empty_graph():
+    G = nx.Graph()
+    rst = nx.tree.random_spanning_tree(G)
+    assert len(rst.nodes) == 0
+    assert len(rst.edges) == 0
+
+
+def test_random_spanning_tree_single_node_graph():
+    G = nx.Graph()
+    G.add_node(0)
+    rst = nx.tree.random_spanning_tree(G)
+    assert len(rst.nodes) == 1
+    assert len(rst.edges) == 0
+
+
+def test_random_spanning_tree_single_node_loop():
+    G = nx.Graph()
+    G.add_node(0)
+    G.add_edge(0, 0)
+    rst = nx.tree.random_spanning_tree(G)
+    assert len(rst.nodes) == 1
+    assert len(rst.edges) == 0