Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If anyone can define a directed graph subdivision with mathematical notation, please post a response.

My second question is: Irrespective from the planar embedded graph or not, is this definition valid or not?

share|improve this question
1  
Your question is rather unclear. Could you explain in more detail what you are asking? –  Hurkyl Apr 5 '13 at 11:11
add comment

1 Answer

up vote 1 down vote accepted

In many cases in graph theory (and mathematics in general), there's not a "best" way to define things. In the case of subdivision of graphs, the choice of notation depends on what it is we want to do. Consider the following situations (for undirected graphs):

  1. For each edge $e_i$, we want to subdivide it $s_i$ times. This is the general situation (up to isomorphism -- if you want labelled graphs, it gets messier).

  2. We want to subdivide each edge.

  3. We want to subdivide an individual edge.

In all three situations it would be better to use different notation. There's no real problem with defining your own notation, e.g., we might define $G^*$ as the graph formed from $G$ by subdividing each edge. As long as we define everything correctly, there's no real problem. The main reason to avoid defining your own notation would be if there is some typical convention for that specific notation.

The situation with directed graphs is much the same (although, we need to be a bit careful as to what we'd consider a subdivision of a directed edge).

Subdivision is defined for any undirected graph, and an appropriately defined notion of subdivision for directed graphs would be defined for any directed graph. Applying the subdivision operation does not require that the graph be planar. However, if you perform subdivision on a planar graph, you get another planar graph, and if you perform subdivision on a non-planar graph, you get another non-planar graph.

I'd also like to mention that there is nothing wrong with simply defining things using words. In fact, in some cases, this approach can be much clearer.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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