Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Where can I find examples of polyhedral embeddings of simple graph with large face-width, such that all the faces have the same length?

By polyhedral embedding I mean an embedding of the graph on a closed 2-dimensional surface, where the boundaries of all the faces are simple cycles, and the intersection of any two faces is either empty, a vertex, or an edge.

The examples should be as non-homogeneous as possible. For example, the Archimedean solids are very homogeneous objects, because all the vertices are equivalent (for any two vertices, there is an isometry that takes one vertex to the other). I admit that I am not using "non-homogeneous" in a clearly defined sense. I am just asking for examples that do not have obvious symmetries.

Note : The face-width of the embedding is the smallest integer $k$ such that there exist $k$ facial walks whose union contains a noncontractible cycle. A facial walk is a walk that bounds a face of the embedding. The length of a face is simply the length of its face walk. Since we are dealing with polyhedral embeddings, all face walks are simple cycles.

share|improve this question
    
What does "as asymmetric as possible" mean? And embedding where? Arbitrary surfaces? three-dimensional space? –  Igor Rivin Jun 15 '12 at 19:44
    
@IgoRivin Sorry. I made some changes to the question (I think your comment is prior to those changes). I have tried to make it more clear. –  becko Jun 15 '12 at 20:07
    
If you are allowing arbitrary surfaces, just take any embedding in the sphere, and if it is too symmetric, add handles randomly in the middle of the faces. Is that somehow not what you are looking for? –  Igor Rivin Jun 15 '12 at 20:50
    
@IgorRivin Adding handles to the sphere without modifying the graph is not what I am looking for. What I need is examples of a graphs that admit polyhedral embeddings of large face-width in which all faces have the same length. The graphs should not be very homogeneous. I hope that's clearer. Do you think I should modify the question some more? –  becko Jun 15 '12 at 22:46
    
I posted a related question here: cstheory.stackexchange.com/q/11717/5982 –  becko Jun 15 '12 at 22:48
show 2 more comments

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.