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

<p>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.</p>

<p>Specifically, for any integers $g$, $d$, and $r$ such that $1/g + 1/d &lt; 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 <strong>both</strong> that every vertex has the same degree <strong>and</strong> 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:</p>

<ul>
<li><p>Roman Nedela and Martin Škoviera.  <a href="http://www.sciencedirect.com/science/article/pii/S0195669800904414" rel="nofollow">Regular maps on surfaces with large planar width.</a>  <em>European J. Combinatorics</em> 22(2):243--262, 2001.</p></li>
<li><p>Jozef Širáň.  <a href="http://plms.oxfordjournals.org/content/82/3/513" rel="nofollow">Triangle group representations and constructions of regular maps.</a> <em>Proc. London Math. Soc.</em> 82(3):513-532, 2001. </p></li>
</ul>

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

<hr>

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

<ul>
<li><p>Every bounded face of $G$ has exactly $g$ edges.</p></li>
<li><p>The outer face of $G$ has an even number of edges; call these the <em>boundary edges</em> of $G$.   (This condition holds automatically when $g$ is even; if $g$ is odd, $G$ must have an even number of bounded faces.)</p></li>
<li><p>It is possible to pair the boundary edges of $G$, <strike>so that the distance in $G$ from any boundary edge to its partner is at least $g$.</strike>  <strong>This condition is not actually enough; the exact condition needed here is unclear.</strong></p></li>
</ul>

<p>Arbitrarily large plane graphs with these properties can be constructed by taking a sufficiently large finite portion of a <a href="http://en.wikipedia.org/wiki/Uniform_tilings_in_hyperbolic_plane" rel="nofollow">regular tiling of the hyperbolic plane by $g$-gons</a>.</p>

<p>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 <em>some</em> closed surface without boundary.  The distance condition on the pairing guarantees that the girth of $G'$ is $g$.</p>

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

CC BY-SA 3.0
2012-06-14T21:23:25.200Z
Also, the graphs you get from this construction are expanders.
Jeffε
CC BY-SA 3.0
2012-06-15T02:12:56.727Z
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?
a06e
CC BY-SA 3.0
2012-06-15T02:13:11.547Z
What is an *expander* graph?
a06e
CC BY-SA 3.0
2012-06-15T20:21:58.350Z
@becko, you should Google before asking :) http://en.wikipedia.org/wiki/Expander_graph
Kaveh
CC BY-SA 3.0
2012-06-17T04:17:03.340Z
@Kaveh Ok. Sorry I missed that :)
a06e
CC BY-SA 3.0
2012-06-14T20:55:57.747Z
2012-06-15T16:45:29.760Z
2012-06-15T16:45:29.760Z
Jeffε
<p>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. </p>

<p>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. </p>

<p>Is there any such method?</p>

<p>Any references to similar problems are also appreciated.</p>

CC BY-SA 3.0
2012-06-14T10:53:37.307Z
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.)
Jeffε
CC BY-SA 3.0
2012-06-14T13:35:11.930Z
@JɛﬀE 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.
a06e
CC BY-SA 3.0
2012-06-15T05:05:39.517Z
@JɛﬀE 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](http://cstheory.stackexchange.com/a/11685/5982). 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?
a06e
CC BY-SA 3.0
2012-06-16T14:56:43.773Z
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
CC BY-SA 3.0
2012-06-17T04:18:42.463Z
@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.
a06e
CC BY-SA 3.0
2012-06-17T15:27:58.103Z
not totally clear on all this but polyhedral embeddings and duals mostly seem to be tied with planar graphs. howeever as far as I know n-regular graphs are not planar in general. true? anyway I think you might start with figuring out if you actually want to limit yourself to planar graphs or not.
vzn
CC BY-SA 3.0
2012-06-17T22:20:11.160Z
@vzn Actually, the notion of embedding applies to many other surfaces besides the plane (for example: the torus, the Mobius strip, etc.). A particular form of embedding is a [2-cell embedding](http://en.wikipedia.org/wiki/Graph_embedding#Terminology) (also a *cellular embedding*), in which all the faces are disks. For any such embedding, one can define a dual, by putting a vertex for each face in the usual way.
a06e
<ds.algorithms><reference-request><graph-theory><co.combinatorics><pseudorandom-generators>
Generating graphs of girth $g$ such that the minimum cycles form a double edge cover
a06e
# Generating graphs of girth $g$ such that the minimum cycles form a double edge cover

(Asked by: username_0 on 2012-06-14)

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.

**Tags:** ds.algorithms, reference-request, graph-theory, co.combinatorics, pseudorandom-generators

> **Comments:**
> **username_1**: 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.)  
> **username_0**: @JɛﬀE 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.  
> **username_0**: @JɛﬀE 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](http://cstheory.stackexchange.com/a/11685/5982). 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?  
> **username_2**: 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.  
> **username_0**: @username_2 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.  
> **username_2**: not totally clear on all this but polyhedral embeddings and duals mostly seem to be tied with planar graphs. howeever as far as I know n-regular graphs are not planar in general. true? anyway I think you might start with figuring out if you actually want to limit yourself to planar graphs or not.  
> **username_0**: @username_2 Actually, the notion of embedding applies to many other surfaces besides the plane (for example: the torus, the Mobius strip, etc.). A particular form of embedding is a [2-cell embedding](http://en.wikipedia.org/wiki/Graph_embedding#Terminology) (also a *cellular embedding*), in which all the faces are disks. For any such embedding, one can define a dual, by putting a vertex for each face in the usual way.  

---

## 1 answers

### Answer by username_1 on 2012-06-14. Score: 4

**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:

* Roman Nedela and Martin Škoviera. [Regular maps on surfaces with large planar width.](http://www.sciencedirect.com/science/article/pii/S0195669800904414) *European J. Combinatorics* 22(2):243--262, 2001.
* Jozef Širáň. [Triangle group representations and constructions of regular maps.](http://plms.oxfordjournals.org/content/82/3/513) *Proc. London Math. Soc.* 82(3):513-532, 2001.

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](http://en.wikipedia.org/wiki/Uniform_tilings_in_hyperbolic_plane).

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.

> **Comments:**
> **username_1**: Also, the graphs you get from this construction are expanders.  
> **username_0**: 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?  
> **username_0**: What is an *expander* graph?  
> **username_3**: @becko, you should Google before asking :) http://en.wikipedia.org/wiki/Expander_graph  
> **username_0**: @username_3 Ok. Sorry I missed that :)  

---

