Hah! Rendering Petersen Graphs as Leveled Hierachal Maps

My current work assignment involves dynamically rendering a directed graph with potentially both cycles and disconnects. A "graph" in this case is a mathematical construct of nodes and connectors; "directed" means the connectors go in one direction, from one node to another. A "disconnected" graph means there may be subgraphs for which one cannot, starting from an arbitrary node, traverse the list of nodes to reach another arbitrary node; there isn't a connector between the two subgraphs. A graph with "cycles" is one where it's possible to end up in a loop, going around and around and around.

Drawing this beast on the screen aesthetically is considered a Hard Problem, but fortunately, there are a number of papers on it with "good enough" solutions. The best seems to be Alaa K. Ismaeel's Dynamic Hierarchical Graph Drawing.

According to the book, there are a few steps one must take: (1) figure out all of the disconnected subgraphs; (2) figure out if any of the subgraphs have cycles; (3) break the cycles, but remember what you broke so you can put it back; (4) figure out at what "depth" each node should be; (5) re-arrange the nodes such that you minimize the number of connectors that "cross" each other; (6) lay out the nodes with enough distance between them. I'm up to (3), and even managed to get it to successfully and correctly break the cycles in a Petersen Graph without damaging the graph's internal logic.

Man, that was fun. Well, on to the rest of it tomorrow.

A postscript on my last post

An interesting note about the paper I linked to in my last post: I've never seen a Ph.D. dissertation with a dedication before. This one was noted:

Full of pride, this thesis is dedicated to: the souls of the Egyptian January 2011 revolution martyrs, the souls of my mother and brother, my father and brothers, my great wife and life partner, and my children.

That's kinda cool.

Pave 9% of Texas; Save America

To absolutely no one's surprise, the National Renewal Energy Laboratory has concluded that paving over Texas would provide the United States with 11 times more electricity than is currently being used.

Sadly, it won't happen. Telling the oil-producing nations of the world to go fuck themselves isn't profitable for the energy market overlords of the United States.