Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Let $g\geq 3$. I need to generate simple graphs $G$ of girth $g$ such that the set of all $g$-cycles forms a double edge cover of $G$ (that is, every edge is shared by exactly two $g$-cycles), and such that the intersection of any two $g$-cycles is either a vertex, an edge, or empty. The generated graphs should be arbitrarily large.

The method of generation should have some randomness to it, but not in a trivial sense. I want to be able to obtain fairly complicated graphs. For example, imagine an $n\times m$ rectangular grid in the plane. If we identify the opposite sides of the bounding rectangle, we obtain a graph that satisfies all of the above requirements for $g=4$. I would qualify this graph as simple.

Is there any such method?

Any references to similar problems are also appreciated.

share|improve this question
3  
So you want the $g$-cycles to be the faces of some polyhedral embedding of the graph onto some surface? (A graph embedding is "polyhedral" if every face of the embedding is a disk, and any two faces share a common vertex, share a common edge, or do not intersect at all.) –  JɛffE Jun 14 '12 at 10:53
    
@JɛffE Yes. If all the $g$-cycles are guaranteed to be faces, and all the faces are guaranteed to be $g$-cycles, then that is an equivalent description. –  becko Jun 14 '12 at 13:35
    
@JɛffE Do you know where I can find distinct 4-regular graphs and their polyhedral embeddings? They don't have to be huge graphs, but I would like to see other graphs that satisfy the properties I requested besides the one I mentioned. I also know that deciding polyhedral embeddability is NP-complete thanks to this answer. In spite of that, I'd also like to know of an algorithm that finds a polyhedral embedding if there is one. Do you know of any resource/paper/... that explains such an algorithm? –  becko Jun 15 '12 at 5:05
    
is there a link between 4 regular graphs and polyhedral embeddings? does someone have a description of that? yrs ago looked up papers on randomly generating regular graphs, there are quite a few, therefore if you can rephrase this question in terms of regular graphs, it might lead to more possibilities. –  vzn Jun 16 '12 at 14:56
    
@vzn Suppose that I have a polyhedral embedding like the one suggested by Jeff. All faces are $g$-cycles. The dual graph obtained from this embedding is $g$-regular. Perhaps this can be inverted: start with a $g$-regular graph and find its dual somehow. That's what I had in mind. –  becko Jun 17 '12 at 4:18
show 2 more comments

1 Answer

My half-baked idea was a little too ambitious. I'm including it below for reference, but the distance condition I specified is not actually sufficient to guarantee large girth.

There are arbitrarily large highly symmetric surface maps with large girth, but published existence proofs are largely based on group theory rather than topology or geometry per se.

Specifically, for any integers $g$, $d$, and $r$ such that $1/g + 1/d < 1/2$, there is a regular surface map in which every face has $g$ edges, every vertex has degree $d$, and every non-contractible cycle on the surface crosses at least $r$ edges. Here "regular" means both that every vertex has the same degree and that for any pair of directed edges, there is an automorphism of the embedding that sends directed edge to the other. Setting $r$ large enough in this construction guarantees that the girth of the graph is $g$. See, for example:

Once you have one such surface map, larger maps with the same girth and degree can be generated by constructing covering spaces.


Here is one (half-baked) way to generate such graphs. Let $G$ be a plane graph with the following properties:

  • Every bounded face of $G$ has exactly $g$ edges.

  • The outer face of $G$ has an even number of edges; call these the boundary edges of $G$. (This condition holds automatically when $g$ is even; if $g$ is odd, $G$ must have an even number of bounded faces.)

  • It is possible to pair the boundary edges of $G$, so that the distance in $G$ from any boundary edge to its partner is at least $g$. This condition is not actually enough; the exact condition needed here is unclear.

Arbitrarily large plane graphs with these properties can be constructed by taking a sufficiently large finite portion of a regular tiling of the hyperbolic plane by $g$-gons.

Finally, to obtain a surface graph $G'$ where every face has length $g$, identify pairs of boundary edges in $G$ according to the pairing described above. The bounded faces of $G$ become the faces of a cellular embedding of $G'$ on some closed surface without boundary. The distance condition on the pairing guarantees that the girth of $G'$ is $g$.

By choosing both $G$ and the pairing more carefully, once can construct arbitrarily large $d$-regular graphs satisfying your girth condition, for any integers $d$ and $g$ such that $1/d + 1/g < 1/2$. Even within these constraints, the construction has lots of degrees of freedom.

share|improve this answer
    
Also, the graphs you get from this construction are expanders. –  JɛffE Jun 14 '12 at 21:23
    
When I identify a pair of boundary edges, how can I be sure that the other pairs of edges are still farther than $g$ away from each other? –  becko Jun 15 '12 at 2:12
    
What is an expander graph? –  becko Jun 15 '12 at 2:13
1  
@becko, you should Google before asking :) en.wikipedia.org/wiki/Expander_graph –  Kaveh Jun 15 '12 at 20:21
    
@Kaveh Ok. Sorry I missed that :) –  becko Jun 17 '12 at 4:17
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.