By way of clearing some space off my whiteboard, here's a drawing that's been taking up space in the middle of it for too long:

( Read more... )

Two papers of mine on the arxiv, one a few weeks old and one newly appearing:

Optimal angular resolution for face-symmetric drawings (with Kevin Wortman). In this paper, we consider drawings of planar partial cubes in which all interior faces are centrally symmetric convex polygons, as in my previous paper Algorithms for Drawing Media from Graph Drawing 2004. Among all drawings of this type, we show how to find the one with optimal angular resolution. The specific motivation was to improve the drawing I showed in this post to be more legible, so that it could be used in my recent paper on squaregraphs with Bandelt and Chepoi. The solution involves the parametric negative cycle detection problem: given a graph in which the edge weights are linear functions of a parameter λ, find the minimum value of λ for which the graph contains no negative cycles. However, unlike my work with Kevin on metric embedding, the parametric graph coming from this problem falls into a special case solved by known algorithms, so we didn't need to invent a new cycle detection algorithm. We're preparing a version of this for journal publication, but the current version doesn't yet have all of the referee's requested revisions incorporated, because I wanted to have a version of this available in order to cite it from the next one:

Graph-theoretic solutions to computational geometry problems. A survey on situations in which geometric problems that are stated without reference to any graph can be solved efficiently by defining some auxiliary graph from the input and performing some graph-theoretic algorithm. For instance, the problem of partitioning a polygon with axis-parallel sides into as few rectangles as possible may be solved in polynomial time by constructing the bipartite intersection graph of its axis-aligned diagonals and finding a maximum matching in this graph. Essentially, this is a paper version of my talk from WG, and I wrote it backwards from the way I usually write papers and talks: usually I write a paper, then later (after it is accepted to a conference) write slides based on that paper, and deliver a talk based on those slides. But this time, I had no paper written when I needed the slides and a talk, so I worked out how to organize the material as part of the process of making slides and giving the talk, and reused the same organization for the paper itself. I used to write survey papers regularly, but lately I've tended to focus that energy on my Wikipedia editing, so it was refreshing to write something like this and not feel constrained to avoid including original research (such as the claim that kinggraphs are 4-chromatic) or original syntheses of existing ideas (the overall point of the survey).

I have another preprint on the arXiv: “Combinatorics and geometry of finite and infinite squaregraphs” (arXiv:0905.4537), with Hans-Jürgen Bandelt and Victor Chepoi. It's a long one, 46 pages, and as the title says is about the properties of squaregraphs, planar graphs in which all the interior faces are quadrilaterals and all the interior vertices have degree at least four.

( Read more... )

I've uploaded another WADS paper to the arxiv today: Orientation-Constrained Rectangular Layouts (with Elena Mumford, arXiv:0904.4312). It's a follow-up to our paper to appear at SoCG on rectangular cartograms, stylized maps in which countries or other regions are replaced by rectangles whose areas represent numerical quantities associated with the regions. In the SoCG paper, we were concerned about area-universality, the ability to morph a cartogram from any set of areas to any other set without changing the orientations of the rectangles, but here we're concerned about a more basic question: which sets of orientations are possible? If, say, I wanted to draw a cartogram for the counties of southern California, it would help readers understand which rectangle corresponds to which county if they could be placed in something resembling their geographic arrangement. For instance, Los Angeles County should be placed above (to the north of) Orange County, or at least not directly below it where San Diego County should be.

( Read more... )

The Fibonacci cube is, as its Wikipedia article says, a graph that is in many respects like a hypercube but with a Fibonacci number of vertices. Its vertices are binary strings with no two consecutive ones, and its edges link pairs of strings at Hamming distance one from each other. The Fibonacci cube formed from bitstrings of length d is an isometric subgraph of a d-dimensional hypercube (the graph of all length-d bitstrings), but it also contains as an isometric subgraph a hypercube of dimension ceiling(d/2) (the binary strings in which only the bits in the even positions can be nonzero). Therefore, the graphs that can be isometrically embedded into Fibonacci cubes are the same as the ones that can be embedded into hypercubes, that is, the partial cubes.

A preprint I recently wrote on this subject with Sergio Cabello and Sandi Klavžar just came out on the arXiv (it's been on the IMFM preprint server for a little longer — if you're interested in graph theory, do check this link out, as it has over 1000 other papers, many of them on graphs). The idea is to investigate the lengths of the bitstrings needed to label a given graph so that graph distance equals Hamming distance and so that no label contains two consecutive ones. That is, we wish to embed graphs isometrically into Fibonacci cubes of minimum dimension. The problem turns out to be NP-hard — it is related to a version of the traveling salesman problem — but can solved exactly in some cases, such as 2d grid graphs. There are also some pretty good approximation algorithms, one of them based on lattice dimension, another based on the xkcd algorithm for traveling salesmen.

I just added an article on Fibonacci cubes to Wikipedia. As the first sentence states, these are graphs that resemble hypercubes but have a Fibonacci number of vertices. Their vertices can be labeled by bitstrings that have no two consecutive one-bits in them, and two vertices are adjacent when their labels differ by one bit.

Something I didn't put in the article, because I didn't find it in any of the published papers I found on these graphs: the Fibonacci cube is the graph of a distributive lattice. If x and y are bitstrings in the Fibonacci cube, the join of x and y can be found by taking their bitwise or in even positions of the bitstring and their bitwise and in odd positions. The meet is the reverse operation, taking the bitwise and in even positions and the bitwise or in odd positions. The top element of the lattice has all ones in the even positions, and the bottom element of the lattice has all ones in the odd positions. And x ≤ y in the lattice ordering if x has a 1 in every odd position that y does and a 0 in every even position that y does.

By Birkhoff's representation theorem, this lattice comes from a partial order. This partial order appears to consist of the bitstrings that (1) have a 1 in an even position, and 1's in all nonadjacent odd positions, or (2) have a 0 in an odd position, and 1's in all other odd positions. Its Hasse diagram is a zigzag path:

10010101    00100101    01001001    01010010
       \     /     \     /     \     /     \
      00010101    01000101    01010001    01010100

It's easy to see from this picture that the number of lower sets in the partial order, and therefore the number of elements of the distributive lattice, satisfies the Fibonacci recurrence: the lower sets that include the final element of the zigzag are defined by a zigzag with one fewer element, and the lower sets that don't include it also don't include the element above it and are defined by a zigzag with two fewer elements.

ETA: Stanley has an article on “The Fibonacci Lattice” in a 1975 Fibonacci Quarterly paper. I was hoping it was the same lattice, since he's defining lattices from posets via Birkhoff and he gets a lattice with a Fibonacci number of elements. But it's not the same poset so it's not the same lattice. I've renamed the title of this post to avoid confusion with his paper.

ETA2: In arXiv:math.CO/9801066 Jim Propp mentions the lattice of independent sets of a bipartite graph. The zigzag lattice is what you get when you apply this construction to a path graph. In general the poset underlying Propp's lattice is formed by directing the edges of the bipartite graph from one side of the bipartition to the other, which in the case of a path graph results in the zigzag poset.

ETA3: It is Stanley after all. Enumerative Combinatorics, exercise 3.23.

Another new paper of mine, “Area-Universal Rectangular Layouts,” with Mumford, Speckmann, and Verbeek (my third recent coauthor named Kevin), just appeared on the arXiv. It's about designing cartograms (stylized maps) in such a way that they can be morphed so that their areas represent arbitrary quantitative data about the regions they depict. I'd like to discuss it in more detail soon, but first I wanted to talk about Birkhoff's representation theorem for finite distributive lattices, the subject of a Wikipedia article I worked on recently and a key tool in our rectangular layout paper.

( Read more... )

This evening I'm reading “Isometric Embeddings of Subdivided Complete Graphs in the Hypercube,” by Beaudou, Gravier, and Meslem [SIAM J. Discrete Math. 22(3): 1226–1238, 2008; there's also an earlier version online from Eurocomb 2007].

( Read more... )

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 received my copy of Knuth's Art of Computer Programming, Volume 4, Fascicle 0, this week. It contains a long section on median graphs, and coincidentally I had just added a long article on median graphs to Wikipedia, so I've been reading that part with great interest.

One of the exercises, 7.1.1 ex.109, caught my attention. In it, Knuth describes the "binary majorization lattice" in which the elements are the n-bit binary numbers and in which x is greater than y if x has at least as many nonzeros as y with x's highest order nonzero bit larger than y's, x's second highest nonzero bit larger than y's, and so on. Here it is as drawn by my algorithm for drawing graphs that can be embedded on an integer grid — here the integer grid turns out to be three dimensional, and the awkward folds in the drawing are there because my algorithm doesn't know any better than to put them in.

( Read more... )

Here's a simple way to label each of the regions of a triangle-free chord diagram by the indices of at most two of the chords.

( Read more... )

I realize it's not exactly day 3 anymore, and it's all a bit of a blur by now, but I thought I'd finish my reporting of the conference regardless. Besides, my flight is delayed so I have plenty of time to write, I'm procrastinating on making slides for my next talk, and it's a good excuse to plug my SODA talk slides and my book, especially since Springer mysteriously failed to do the latter at their exhibit table.

( Read more... )

For more on ALENEX/ANALCO and SODA, see my previous entries (I, II, III), Suresh's (I, II, III), Michael Mitzenmacher (I, II), and Hal Daume.

Draw a graph, having as its vertices the double permutations (sequences of two copies each of the numbers 0 through n − 1 such that the first copies of each number are in sorted order), and connect by an edge two sequences that differ by a single transposition of adjacent elements. What is the structure of this graph? I was naively expecting a 1×3×5×7... grid, coming from the enumeration of these objects as double factorials, but no.

( Read more... )

A chord diagram is formed by choosing some 2n points on a circle (say, at the vertices of a regular polygon) and then connecting them in pairs. It can be represented as a double permutation: a sequence of the 2n values 0,0,1,1,2,2,..., where each value appears twice, and where renumbering the values but keeping the same pairing forms a sequence that is considered to be equivalent. Simply place the values in clockwise order at the chosen points of the circle, and connect pairs of points with equal labels. For instance, the double permutation 0,0,1,2,3,1,3,2, placed clockwise starting at the top vertex of a regular octagon, produces the chord diagram

( Read more... )

On learning of the lattice structure of the system of rooted spanning trees of a plane graph, I was hopeful that the theory would extend in a nice way to unrooted trees. For each choice of root and outer face, we have a distributed lattice, and the set of state transition systems formed in this way for different roots in a fixed graph share the same set of vertices and many of their edges. Different choices of root and outer face lead to different orientations on the edges, but we already know of an unoriented structure that generalizes distributed lattices, namely media. If we form a state transition system in which the states are the spanning trees of a plane graph, and the transitions are formed by replacing one of the edges at any vertex by a cyclically adjacent edge at the same vertex, is the result a medium?

The short answer: no, not generally. The longer answer:

( Read more... )

I'm far behind on my reading, so consider this as the first installment in my attempts to catch up.

( Efficient dual pairs of spanning trees )

( Robust de-anonymization of large datasets )

( Being first and ranking journals )

( Hinged dissections exist )

( Tribes of cubic partial cubes )

Video from my talk in Bled, now online. (If you want to follow along on the talk slides, they're here.)

They also have videos up from the other invited speakers at Bled'07.

The Media Theory book is done and sent to the publishers. Which makes, I think, a good excuse to say a little of what it's about.

In short, a medium is a system of states and tokens that act on the states, like a deterministic finite state machine but without the complication of initial and final states, and with some extra axioms that the state transitions must satisfy. Because of these axioms, media can be shown to be equivalent in theory to partial cube graphs, but the automata-theoretic viewpoint leads to a different emphasis of topics.

There is plenty of material in the book about the sorts of things you'd expect me to be interested in: graph theory, geometry (particularly hyperplane arrangements, the regions and region adjacencies of which form media), graph drawing, and the design and analysis of algorithms. But my coauthors Falmagne and Ovchinnikov are, respectively, a cognitive scientist and mathematician, so the book also has plenty of foundational material on how to define and characterize media, how to use them to model important concepts from order theory (total orders, partial orders, weak orders, interval orders, etc), and how these concepts can be applied in the social sciences.

I've put up a new version of PADS after making some bugfixes to the partial cube recognition code, which the two graphs below gave some trouble to. The left one was causing it to crash, and the right was incorrectly reported as being a partial cube; the correct behavior in both cases was to report that the graph is not a partial cube. Now fixed and added to the test cases within the code. Fortunately, both bugs involved minor implementation details rather than any issues with the algorithm itself.

Talk slides from my talk on partial cubes this morning at Bled'07 are now online. (Warning: 3.3Mb pdf file.) Supposedly video from the talk will eventually appear at videolectures.net.