0
$\begingroup$

A graphical representation of a planar graph divides the plane into regions or meshes (as they are called in certain applications, e.g. in circuit theory).

Yes, the above fact is intuitive, but what I couldn't find in common textbooks on graph theory is a formal definition of mesh related to the definition of graph as a pair of sets of vertices and edges. In particular, is there a formal definition of mesh (or region) of a graph which does not rely on its graphical representation or which relies in a formalization thereof?

$\endgroup$
2
$\begingroup$

If the graph is already drawn on the plane, the regions are connected components of the set complement of the union of the curves presenting the edges. Sometimes you may define the regions combinatorially. For example, if you have a convex polytope, any face is bounded by a simple cycle such that removing it from the graph preserves the connectivity. And vice versa, any such a cycle is a boundary of a face. This allows to reconstruct the structure of faces knowing only combinatorial structure of the graph. In general you can not do it, as an example of the graph "triangle ABC plus edges AD, AE" shows.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.