I have an arbitrary collection of nodes connected by edges. I am trying to find a good way to tell if an edge/vertex is on the border or not.

The red nodes and blue lines are considered on border. Black lines and black nodes are considered interior.

enter image description here

All nodes are fixed to points on the Cartesian plane. It is a planar graph (no edges will cross over each other. They will intersect only at a node). Always one graph / connected shape in total (as opposed to multiple independently connected components).

  • $\begingroup$ Will your vertices always correspond to lattice points? If so, you could say that a vertex is interior iff it has degree 4. If not, I don't think there's a way to define the border/interior. $\endgroup$ – DylanSp Feb 2 '16 at 21:26
  • 7
    $\begingroup$ An "arbitrary collection of nodes connected by edges" is otherwise known as a graph. Is the graph planar, and are you given an embedding? If you're not given an embedding, there's no way to answer this question, because a graph may have multiple embeddings in which different nodes and edges are interior/exterior. $\endgroup$ – Tom van der Zanden Feb 2 '16 at 21:26
  • $\begingroup$ @DylanSp What do you mean by "always correspond to lattice points"? It will look like a bunch of squares, yes. But as for degree four, look at the graph above, middle row, far right; those vertices have degree 4, do they not? $\endgroup$ – user213846 Feb 2 '16 at 21:27
  • $\begingroup$ @TomvanderZanden What do you mean by embedding? It will always look something like the picture above (like a grid graph, or at least part of one), square-like structure. I don't know the formal terminology. $\endgroup$ – user213846 Feb 2 '16 at 21:28
  • $\begingroup$ @TomvanderZanden Okay I googled it. Yes it will be planar (no edges cross over each other; they always intersect at a node/vertex) $\endgroup$ – user213846 Feb 2 '16 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.