Can regular maps, no matter their complexity, be topologically transformed into circular maps or rectangular maps?

For rectangular maps, for example, I intend maps that are made from overlapping rectangular faces as shown here: Rectangular and circular maps. And here is the proof.

I don't know if this is a new result or not (I did not find it on internet) and I don't even know if this may be useful to help finding a "pencil and paper", elegant and human checkable proof for the four color problem.

What is known about this? Has it been studied before?

  • 1
    $\begingroup$ Hi Mario. cstheory is a Q&A site and is not for opinions. (You seem to link to a proof answering your question, so this doesn't seem to be a real question.) $\endgroup$ – Kaveh Mar 31 '11 at 21:48
  • $\begingroup$ I apologize. It was my first question on this website. Just wanted to ask if a similar result is already known. The question is: Can regular maps, no matter the complexity, be topologically transformed into rectangular maps (maps made from overlapping rectangular faces)? Do you think this is still off topic? In case, I renew my apology. $\endgroup$ – Mario Stefanutti Mar 31 '11 at 22:44
  • 3
    $\begingroup$ I guess I can't leave this as an answer because this is closed already. But the tool you need to prove that any 3-connected 3-regular planar graph can be converted into a rectangular map as in your picture is called the "canonical ordering" in graph drawing. See Kant, "Drawing planar graphs using the canonical ordering", Algorithmica 1996, or Badent et al, "More canonical ordering", JGAA 2011, jgaa.info/accepted/2011/BadentBrandesCornelsen2011.15.1.pdf $\endgroup$ – David Eppstein Apr 1 '11 at 0:01
  • 2
    $\begingroup$ no need for apologies :), you haven't done anything wrong, closing/reopening posts is not a big deal, you can rephrase your post to make it a real question. (suggestions: "what is known about this? has it been studied before? ...".) $\endgroup$ – Kaveh Apr 1 '11 at 0:05
  • $\begingroup$ @David, I am reopening it so you can post it as an answer. $\endgroup$ – Kaveh Apr 1 '11 at 0:08

Your "proof" is too vague to convince me, but here's a description of how these maps can be formed. Given a 3-regular 3-connected planar graph, its dual is a maximal planar graph. Every maximal planar graph has a canonical ordering (see references in my earlier comment): an ordering on the vertices of the graph such that the following properties hold:

  • The first three vertices in the ordering are adjacent
  • Each prefix of three or more vertices in the ordering defines a subset of the vertices whose boundary is a simple cycle
  • Each vertex after the first three has as its neighbors a contiguous path of the boundary cycle of the previous vertices

This should allow you to define your rectangular drawing top down. Find a canonical ordering of the dual graph, and make side-by-side rectangles for the first two dual vertices in the canonical ordering (corresponding to two adjacent faces in your graph). Then, add rectangles one by one in the given ordering, below these first two rectangles. For each successive rectangle r, corresponding to a dual vertex v, choose the top vertices on the left and right sides of r to be points on the rectangles corresponding to the endpoints of the contiguous path of neighbors of v from the canonical ordering.

The invariant that makes this work, at each step, is that the boundary cycle of the canonical ordering is exactly the same as the sequence of rectangles that you would see if you stood underneath your drawing and looked upwards.

The circular map should be exactly the same, just starting at the outside and working inwards.

As for the other questions at the end of your post: is this interesting? I don't know. There's some related work in the graph drawing community on representing maps by regions with rectilinear boundaries; the phrase to search for is "rectilinear cartogram". You'd have to show some concrete advantage of your method over previous rectilinear cartogram construction methods such as the one in http://citeseerx.ist.psu.edu/viewdoc/download?doi= — but suggesting ways to achieve this is probably beyond the scope of this exchange.

| cite | improve this answer | |
  • $\begingroup$ I will definitely get the paper you suggested. I knew of "Rectangular grid drawings of plane graphs", which seems related. I think the advantage, respect to rectilinear cartogram in general, is related to the sequential nature of the graphical representation: rectangles are placed at consecutive y-coordinates. It fits very well into computers. If interested, it can be seen in action here: youtube.com/user/mariostefanutti and downloaded from sourceforge.net/projects/maps-coloring. My next steps are: read the paper + go through your description + work on my proof being vague. $\endgroup$ – Mario Stefanutti Apr 1 '11 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.