Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

April 23, 2016

Polygonal Decompositions of Surfaces

Posted by John Baez

If you tell me you’re going to take a compact smooth 2-dimensional manifold and subdivide it into polygons, I know what you mean. You mean something like this picture by Norton Starr:

or this picture by Greg Egan:

(Click on the images for details.) But what’s the usual term for this concept, and the precise definition? I’m writing a paper that uses this concept, and I don’t want to spend my time proving basic stuff. I want to just refer to something.

I’m worried that CW decompositions of surfaces might include some things I don’t like, though I’m not sure.

Maybe I want PLCW decompositions, which seem to come in at least two versions: the old version discussed in C. Hog-Angeloni, W. Metzler, and A. Sieradski’s book Two-dimensional Homotopy and Combinatorial Group Theory, and a new version due to Kirillov. But I don’t even know if these two versions are the same!

One big question is whether one wants polygons to include ‘bigons’ or even ‘unigons’. For what I’m doing right now, I don’t much care. But I want to know what I’m including!

Another question is whether we can glue one edge of a polygon to another edge of that same polygon.

Surely there’s some standard, widely used notion here…

Posted at April 23, 2016 4:54 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2877

14 Comments & 0 Trackbacks

Re: Polygonal Decompositions of Surfaces

Well, in CW complexes, one doesn’t ask the attaching maps to be at all nice in any way, so long as they are continuous. Asking instead that they be cofibrations will mean the 2-cells internally look like polygons, but will also rule out glueing two sides of one such cell, AND ugons (in case that matters)… it also rules out monogons by accident, because it rules out their boundaries; but digons would be available.

Just to clarify your question for people knowing better than me: are you asking primarily to follow what people mean when they don’t spell out their sense of polygonal decomposition, or so you know what to call them for other folk to read?

Posted by: Jesse C. McKeown on April 23, 2016 8:12 PM | Permalink | Reply to this

Re: Polygonal Decompositions of Surfaces

Jesse wrote:

Just to clarify your question for people knowing better than me: are you asking primarily to follow what people mean when they don’t spell out their sense of polygonal decomposition, or so you know what to call them for other folk to read?

I want to know 1) what to call them in a paper I’m writing, and 2) a reference to point to, that works out the theory so I don’t have to.

There seems to be a well-established literature on ‘triangulated surfaces’, so that you can say this phrase and expect people to understand. But the literature on ‘decompositions of surfaces into polygons’ seems diffuse and murky: I feel I haven’t found the locus classicus.

I really enjoyed Hog-Angeloni, Metzler, and Sieradski’s Two-Dimensional Homotopy and Combinatorial Group Theory back when I was studying ‘spin foams’. They had a lot of nice terminology for quite general spaces made of polygons, not necessarily manifolds. That’s what I needed then.

But forcing my readers through this stuff now, when I just want to talk about a compact surface chopped into polygons, seems a bit sadistic.

Hmm, this looks promising:

Posted by: John Baez on April 23, 2016 9:03 PM | Permalink | Reply to this

Re: Polygonal Decompositions of Surfaces

You can specify such things by simply discussing a properly embedded finite graph (i.e. 1-dimensional finite CW-complex), say with smooth edges, in the surface such that each face (complementary connected component) is homeomorphic to an open disc.

Posted by: Scott Taylor on April 23, 2016 8:30 PM | Permalink | Reply to this

Re: Polygonal Decompositions of Surfaces

This sounds almost like what I want. However, I don’t want to have to prove all the supposedly obvious consequences of this definition: someone should have done it, and I should just refer to them.

I have a couple issues with the concept here. First, what does ‘properly’ embedded mean?

Second, I can take a sphere and embed a graph in it with two vertices x,yx,y, one edge f:xyf: x \to y and one edge g:xxg: x \to x. Both components of the complement are homeomorphic to open disks. To walk around one of these components I follow the loop gg, but to walk around the other I follow the loop gff 1g f f^{-1}, which is a bit irritating.

In other words, if I treat the sphere as made of vertices, edges and faces, one ‘face’ is a unigon while the other is a triangle with two edges glued together.

I don’t need unigons for what I’m doing, but I can live with them. For what I’m doing, faces with edges glued together will not work: I’ll need to rule them out.

Posted by: John Baez on April 23, 2016 9:16 PM | Permalink | Reply to this

Re: Polygonal Decompositions of Surfaces

It also sounds to me like the concept of embedded graph is what you’re looking for, which is also called a “map”. (Here, “proper” embedding just means that the edges of the graph are not allowed to cross each other.)

Any map on a compact oriented surface without boundary can also be represented up to isomorphism by the data of a combinatorial map, i.e., a set DD equipped with a pair of permutations vv and ee such that 1. ee is a fixed-point free involution, and 2. the group v,e\langle v,e\rangle acts transitively on DD. Some of the standard references for this are:

  • J. Edmonds (1960), A combinatorial representation for polyhedral surfaces, Notices Amer. Math. Soc. 7, 646.
  • A. Jacques (1970), Constellations et graphes topologiques, Colloque Math. Soc. Janos Bolyai, 657-672.
  • Gareth A. Jones and David Singerman. Theory of Maps on Orientable Surfaces. Proceedings of the London Mathematical Society 37:273–307, 1978.

In particular Jones and Singerman’s paper does the work of formally connecting the topological definition of map to the algebraic one by proving an equivalence of categories.

> For what I’m doing, faces with edges glued together will not work: I’ll need to rule them out.

In terms of graph embeddings, I think that this condition is equivalent to asking that the underlying graph be 2-connected. For example, Tutte restricted the definition of “map” to only include such embeddings in A census of Hamiltonian polygons, and he began by proving that their underlying graph must be 2-connected.

Posted by: Noam Zeilberger on April 23, 2016 10:26 PM | Permalink | Reply to this

Re: Polygonal Decompositions of Surfaces

It is worth mentioning that Jones and Singerman’s work links up with Grothendieck’s Dessins d’enfants, for which look on Wikipedia, or Google it.

(The basic graphs on surfaces stuff also has connections with Coxeter and Moser’s book: Generators and Relations for Discrete Groups. This stuff is good fun to teach as well, as it links several elementary parts of maths to something that is far from elementary in its consequences.)

Posted by: Tim Porter on April 26, 2016 7:37 AM | Permalink | Reply to this

Re: Polygonal Decompositions of Surfaces

Excellent! Thanks for the references, Noam!

I really just need the combinatorial structure; the topology is just a convenient way for people to visualize what’s going on.

I fear that no matter what I do, I run the risk of making things seem more tricky than they are — or else leaving things a bit vague. I guess pictures will help save the day.

Posted by: John Baez on April 23, 2016 11:16 PM | Permalink | Reply to this

Re: Polygonal Decompositions of Surfaces

The way I meant the terminology to work, “embedding” means that the map of the abstract graph into the surface is a homeomorphism/diffeomorphsim onto its image and “proper” meant that the graph intersects the boundary of the surface exactly in the boundary of the graph (i.e. valence one vertices).

Posted by: Scott Taylor on April 24, 2016 12:11 AM | Permalink | Reply to this

Re: Polygonal Decompositions of Surfaces

Okay, thanks! I looked up ‘proper embedding, and guessed something like this. I’m not doing surfaces with boundary, so I can avoid this nuance. Right now my paper says this:

Suppose we have a graph XX embedded in a compact surface SS. The complement SXS - X is the disjoint union of finitely many open sets whose closures we call faces. We demand that the faces are closed disks embedded in SS.

But I’ll probably add a bit of clarification. Everything in the paper is topological, not smooth, and I’ve said how a graph is a topological space, but it may allay some worries about ‘wildness’ to assure people that the edges are mapped in smoothly.

I don’t think this actually matters for the combinatorial structure: that is, I think that whether we interpret my words above smoothly or topologically, we get the same class of combinatorial maps. But I want to make it clear that nothing nasty is allowed.

Posted by: John Baez on April 24, 2016 12:33 AM | Permalink | Reply to this

Re: Polygonal Decompositions of Surfaces

> I think that whether we interpret my words above smoothly or topologically, we get the same class of combinatorial maps.

The paper by Jones and Singerman cited above proves something to that effect, so long as the surfaces you are working with are oriented. Specifically, their paper proves that “every map \mathcal{M} [on an orientable surface] is isomorphic to some canonical map ¯\overline{\mathcal{M}} on a Riemann surface 𝒮¯\overline{\mathcal{S}} (this justifies an early tradition of regarding maps as lying on Riemann surfaces).”

Are your surfaces oriented/orientable? If not, there are other combinatorial representations of maps which apply to unoriented/non-orientable surfaces.

(p.s., sorry, Scott, that I mistranslated your terminology in the previous comment.)

Posted by: Noam Zeilberger on April 24, 2016 10:53 AM | Permalink | Reply to this

Re: Polygonal Decompositions of Surfaces

Yes, they’re oriented! Thanks!

I’ll explain what all this is for in a while. For now, anyone who is really curious can read the many comments here:

But I’m trying to put together something more organized.

Posted by: John Baez on April 24, 2016 4:52 PM | Permalink | Reply to this

Re: Polygonal Decompositions of Surfaces

Hi John,

Your situation most reminds me of what Rourke and Sanderson would call “cell complexes” or “ball complexes.” Have a look at their Introduction to Piecewise-Linear Topology, first four or five pages of chapter 2. They might also develop this in more detail in their book with Buoncristiano, but I don’t have that handy.

Posted by: Greg Friedman on April 24, 2016 9:01 AM | Permalink | Reply to this

Re: Polygonal Decompositions of Surfaces

Thanks!

Posted by: John Baez on April 24, 2016 9:00 PM | Permalink | Reply to this

Re: Polygonal Decompositions of Surfaces

Useful notions might be: polyhedral complexes realizing your surface. A 2D polyhedral complex is a collection cells: points (o-cells) edges (1-cells) and polygons (2-cells) s.t. a face of a cell is also a cell and the intersection of two cells is a cell. Another (more general) useful notion is that of regular CW complexes where the closure of an open cell is homehomorphic to a close ball. Here the intersection of cells can be a union of several cells. If you want to allow cells whose intersection is only part of a face then I am not sure what is the right object.

Posted by: Gil Kalai on April 28, 2016 3:39 PM | Permalink | Reply to this

Post a New Comment