2
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ What does "as asymmetric as possible" mean? And embedding where? Arbitrary surfaces? three-dimensional space? $\endgroup$
    – Igor Rivin
    Commented Jun 15, 2012 at 19:44
  • $\begingroup$ @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. $\endgroup$
    – valle
    Commented Jun 15, 2012 at 20:07
  • $\begingroup$ 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? $\endgroup$
    – Igor Rivin
    Commented Jun 15, 2012 at 20:50
  • $\begingroup$ @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? $\endgroup$
    – valle
    Commented Jun 15, 2012 at 22:46
  • $\begingroup$ I posted a related question here: cstheory.stackexchange.com/q/11717/5982 $\endgroup$
    – valle
    Commented Jun 15, 2012 at 22:48

0

You must log in to answer this question.