Is there a way to find the boundary of a graph?

[Linus-Foley]

Does anyone know of a way to compute the 'boundary' (not sure if this is the right terminology) of a graph, using networkx? This image displays what I'm after:

The blue path is what I'm referring to as the 'boundary'. I'm aware of edge_boundary() and node_boundary() but these seem to be dependent on having the right set of nodes to begin with.

Also, for my case I am only working with graphs similar to the above, where triangles can be formed by the edges in such a way that no edges overlap. I believe that the triangular property results in the existence of one boundary.

[eriknw]

These are indeed typically called boundary edges. If you know the graph is a triangular mesh, then the boundary edges are the edges that are only part of a single triangle. I know how to do this in terms of linear algebra for undirected graphs:

With scipy.sparse

a = nx.to_scipy_sparse_array(G, weight=None)
boundary_edges = (a @ a.T * a == 1).nonzero()

With python-graphblas

import graphblas as gb
from graphblas.semiring import plus_pair

A = gb.io.from_networkx(G, weight=None)
boundary_edges = plus_pair(A @ A.T).new(mask=A.S).select('==', 1).to_edgelist()
# or `.to_coo()` instead of `.to_edgelist()`

For large graphs, GraphBLAS will be much faster and use much less memory than using scipy.sparse. GraphBLAS will be faster, because it is multithreaded (and really fast generally), and it will do less work. When using scipy.sparse arrays, it computes the intermediate matrix a @ a.T, which may be very large. GraphBLAS, however, applies an output mask during the matrix multiply, which results in a much smaller array. Taking the transpose (a.T or A.T) is unnecessary if the graph is undirected (and the adjacency matrix is symmetric).

I don't know if NetworkX has any good ways to do this. I'm sure there are ways to do this in pure Python too.

[Linus-Foley]

This worked beautifully, thank you!

[dschult]

This concept of a "boundary" of a graph only applies to "Planar Graphs" (graphs that can be drawn in a plane without having any edges cross). In such a graph, we identify "faces" of the planar regions surrounded by edges. And one of the faces is the region that extends to infinity. So another way to discuss what you are talking about is the set of edges that are incident to the face that extends to infinity.

That also brings up another issue with how your problem is stated. If we only know the nodes and edges of the graph, we can't determine which of the faces is the one that extends to infinity. Said another way, in your picture it is clear to humans what the outer-most ring of edges is. But that is because the picture includes much more information than the nodes and edges of the network. In our planar graph layout algorithm we try to select the region with the most edges as the face that extends to infinity. But that is an arbitrary choice. In your drawing, if we move the upper-right point down to the lower left and morph the node positions along the way so that the top trinagle inside the drawn boundary now extends to infinity and the infinite "outside" region becomes a finite polygonal region. Then humans would give a different 3-edge boundary of the graph.

So, what should the computer do? Ask for more information. How do you want to select the face that is going to infinity -- and thus whose edges are the boundary edges of the graph?

I would guess you are considering a case where the node positions are given somehow. In that case, a geospatial library is probably better built to handle this kind of question. If you don't have node positions, then you will need to figure out which region to consider. If your graph is triangulated, but the "outside" region is not, then your network is not triangulated. You could add a node positioned at infinity and triangulate the resulting graph -- each new triangle would bring in two new edges, and the third edge of each new triangle would be in the boundary you are looking for. There might be a more effective way to do this -- I'm just making it up as a promising approach.

NetworkX has routines and a data structure for PlanarEmbeddings. And some related algorithms for making a graph "chordal". You might be able to take advantage of these functions to build an algorithm that determines the planar boundary of the graph. But before doing too much of that, sit down and try to figure out what you mean by the boundary -- what information besides the nodes and edges do you have and how will that play a role in your algorithm. Because without that information, you won't be able to find the boundary.