The list of Graph Drawing 2008 accepted papers is out.

Unlike some larger theory conferences, Graph Drawing allows program committee members to submit papers (but not to see or contribute to the deliberations on their own submissions) because otherwise it would be difficult to field a program committee without cutting off a large fraction of the conference's contributors. Therefore, although I was on the PC, I also have some papers in the list: two on xyz graphs and greedy embedding that I've already discussed here, and one additional short paper, “Isometric Diamond Subgraphs.” I don't want to spend a lot more space describing this last one, but let me just show a couple pretty pictures.

( Read more... )

There's plenty of other interesting research to be presented at the conference, so come to Crete and find out all about it!

I just returned from a very pleasant several-day visit to Tucson, at the invitation of Stephen Kobourov, to visit him and Alon Efrat. I spoke Wednesday morning about xyz graphs; my talk slides are here.

Wednesday afternoon, we visited the Sonora Desert Museum, and then took a short (one hour) hike into Saguaro National Park, where Stephen showed me some petroglyphs at a site he knew of. We had been planning to do this Sunday, but it rained that day, after which the weather was beautiful. Photos here and here.

The Foster census lists cubic symmetric graphs; that is, graphs in which the vertices all have three edges, and some symmetry takes any directed edge to any other directed edge.

Among these graphs, the one with 24 vertices clearly deserves a name, as Ed Pegg wrote in his online MAA column in 2003. Naming it after a person is no good: the first person to write about it was Foster [Foster, R. M. (1932), "Geometrical circuits of electrical networks", Transactions of the American Institute of Electrical Engineers 51: 309–317], who gives his name to the whole list of cubic symmetric graphs, and apparently the second was Coxeter [Coxeter, H. S. M. (1950), "Self-dual configurations and regular graphs", Bulletin of the American Mathematical Society 56: 413–455] for whom plenty of graphs are already named. For lack of a better name, I'm going to call it the Nauru graph, because the flag of Nauru has a 12-point star greatly resembling the one in one of the standard drawings of this graph.

( Read more... )

Some recent uploads to arxiv.org that have caught my attention:

Lens sequences, by J. Kocik, arXiv:0710.3226. ( Read more... )

Generalizations of Schöbi's tetrahedral dissection, by Sloane and Vaishampayan, arXiv:0710.3857. ( Read more... )

Simple, linear-time modular decomposition, by Tedder, Corneil, Habib, and Paul, arxiv:0710.3901. ( Read more... )

The lonely vertex problem, by D. Frettlöh and A. Glazyrin, arxiv:0710.4870. ( Read more... )

Triangular peg solitaire unlimited, by G. I. Bell, arxiv:0711.0486. ( Read more... )

Permutations defining convex permutominoes, by Bernini, Disanto, Pinzani, and Rinaldi, arxiv:0711.0582. ( Read more... )

I've now run my xyz-graph testing code on the graphs of up to 56 vertices in the Foster Census of cubic symmetric graphs. That's about the limit of how large a graph it can handle before I run out of patience.

( Read more... )

Ed Pegg recently asked me whether various cubic Hamiltonian graphs were xyz graphs, and to test this out I added some code for LCF Notation to GraphExamples.py in PADS along with several specific graphs that can be described using this notation.

( Read more... )

Inspired by my previous post on a truncated-cube Cayley graph for permutations on four elements, I tried looking at similar presentations for larger permutation groups.

( Read more... )

The Topology of Bendless Three-Dimensional Orthogonal Graph Drawing, a new paper I wrote, is now online at the arxiv. This is basically the material from a series of blog posts I made on "xyz graphs", written up formally in more detail and formatted as a paper, although there are a few additional results not in the posts.

Together with my papers on flip graphs and simplicial arrangements, this marks the third time I've written a series of blog posts on a subject before realizing that my half-baked noodlings had somehow morphed into the content for a paper. Or maybe the fourth time, if you count the triangle center paper that grew out of some web animations I made.

Although I don't tend to get a lot of feedback on my more technical posts, something about the blogging process makes working this way feel more collaborative than when I'm working on a problem by myself without blogging about it. Just as I would when I'm discussing a problem at the whiteboard with someone in my office, I'm spending less time purely thinking about a problem and more time drawing pictures and trying to explain clearly what I'm thinking. And I think that it's helpful to interleave this sort of communication with the more traditional style of doing research while staring at walls or taking walks or taking showers or trying to fall asleep: it helps clarify the parts of the problem I'm working on that I already understand and focus my attention on the parts I don't. I know, I could just keep a notebook instead of posting things on blogs for the world to read, and sometimes I do, but that wouldn't supply the same kind of pressure to write in a way that would (I hope) be understandable to other people. And when I do eventually write a paper on something I've blogged about, the writing stage of the process is easier, because I have the posts and their illustrations to use as content.

I'm wondering that I don't see more of that sort of thing from other math or theoretical CS bloggers, actually — the category theorists have an active collection of blogs with this sort of content, but it seems to be less common behavior among the rest of us. I suppose it's natural to worry about being scooped; I haven't yet found that to be a problem with my own blog posts, but, to be honest, I haven't been posting the ideas that I felt from the start had a strong chance of turning into papers, only the ones that started out feeling too small and then grew. And anyway, if one's blog posts succeed in getting someone else interested in the same subject, I'd think the more likely outcome would be a chance at collaboration and co-authorship.

I can now prove that recognizing whether a given 3-regular graph is an xyz graph (that is, whether it can be embedded in a 3d integer grid so that each grid line contains at most two points and so that all edges are oriented along grid lines) is NP-complete. The same reduction also shows that it is NP-complete to determine whether an arbitrary graph may be embedded in a 3d grid so that two vertices are adjacent if and only if they lie on a common grid line, because the xyz graphs are exactly the triangle-free cubic graphs of this type.

( Proof sketch )

ETA: Relatedly, the graphs embeddable in a 2d grid such that two vertices are adjacent if and only if they share a row or column are the line graphs of bipartite graphs, known to be polynomially recognizable and one of the important building blocks of perfect graphs. Of course, as xyz graphs are triangle-free and not always bipartite, they cannot all be perfect. The line graphs of tripartite graphs (NP-complete to recognize via 3-coloring) can be realized geometrically as intersection graphs of axis-aligned lines in 3d.

The 32-vertex graph shown below (with edges connected around the boundary of the drawing by matching pairs of letters) is an xyz graph in two different ways.



( Read more... )

An st-orientation of an undirected graph is an assignment of a direction for each edge, turning it into a directed acyclic graph with one source and one sink. For any biconnected graph such an orientation may be found in linear time via depth first search: For each DFS tree edge (u,v) (where u is the parent), orient (u,v) oppositely to the DFS tree edge down from the low vertex of v into the subtree containing u and v. For each nontree edge (u,v) (where u is the top vertex), orient (u,v) the same as the DFS tree edge down from u into the subtree containing v. I've been meaning to add this to PADS for a while, after lecturing on it as part of the graph drawing section of my undergraduate graph algorithms class this quarter, but it's now there (in Biconnectivity.py) after I found motivation in a connection to xyz graph recognition:

Any biconnected 3-regular graph can be partitioned in at most 2^n/2-1 different ways into three matchings. The idea of the proof is to process the vertices in a topological ordering (also added to PADS, in TopologicalOrder.py) of an st-orientation, and when processing each vertex choose how to assign the adjacent edges to the three matchings, consistently with prior choices. We only have to make a binary choice at the n/2-1 vertices with one incoming and two outgoing edges; at all other vertices there is no choice to be made. This leads to an O(n 2^n/2) time algorithm for recognizing xyz graphs, which I implemented as part of PADS in xyzGraph.py.

( Read more... )

It turns out there's a very simple characterization of xyz graphs: if a graph G is embedded on a surface, then that embedding can be represented as an xyz graph, with the surface represented via the flat polygons of the xyz graph, if and only if: (1) every face of the embedding is a disk without repeated vertices, (2) if any two faces intersect, they do so in an edge, and (3) the faces can be 3-colored.

For instance, the following three tori (drawn as rectangles with periodic boundary conditions) all form xyz graphs. The left one is the nine-hexagon torus we've already seen before, center is another twelve-hexagon torus, and right is a torus embedding of the four-dimensional cube-connected-cycles network (and also a GEM for K_4,4).



( Read more... )

For lack of a more creative name, I've decided to call the graphs I discussed a couple days ago, formed from point sets intersecting any axis-parallel line in zero or two points, xyz graphs. The ones that fit in a 2×n×n grid are just the prisms over even polygons. Up to graph isomorphism there are only three that fit in a 3×3×3 grid:



Left to right, the flat polygons of these graphs form a projective plane closely related to the one in the previous posting, a planar graph with nine faces, and a torus with nine hexagonal faces. The enumeration of such graphs within a 4×4×4 grid should be well within computational reach since each such graph can be determined by the presence or absence of vertices within a 3×3×3 subgrid.

( Orientability equals bipartiteness )

( Connectivity )

( Arbitrary genus )

( High genus in small cubes )

Suppose we have a point set S in 3d such that any line parallel to a coordinate axis intersects S in either zero or two points. If we draw a graph by connecting pairs of points on the same line, we get a 3-regular graph, such as the one below.



What other properties must such a graph have? For instance, they can't contain a K_2,3 subgraph, a triangle, or a pentagon. After thinking some more about the inverse permutohedron example I posted the other day, I started to wonder, do such graphs always form partial cubes?

( Read more... )

The n! permutations of the vector (1,2,3,...,n) lie on a hyperplane, so their convex hull forms an (n-1)-dimensional shape, known as the permutohedron. E.g., the three-dimensional permutohedron, representing the permutations on four items, is below.

( Permutohedron )

Two permutations are connected by an edge in this shape if they differ by swapping two items that differ in value by one. The graph of vertices and edges of this shape is one of the standard examples of partial cubes, although it doesn't look very cubical in this form.

But now imagine the same graph, rearranged by moving every permutation to its inverse. What do you get?

( Inverse permutohedron )