Old and busted: fake conferences that scam money out of academics using high registration fees, accept everything rather than subjecting submissions to any sort of peer review, but actually exist: you can attend them, meet the other dupes, and get a proceedings.

The new hot trend: fake conferences that don't exist, come with (nonexistent) paid travel expenses to invited speakers and, presumably, scam money out of academics by getting them to send their banking data to the organizers.

Via BoingBoing.

When I'm in the heat of coming up with new ideas on a research project I have a bad habit of sending an email to my collaborators and then, a minute or an hour or a day later, another and another, correcting or contradicting or elaborating on the previous ones, until it can be difficult to figure out which parts of what I sent were important or bogus or relevant. Wouldn't it be better to have a system that's sort of like email, in that it allows one to send messages that only one's trusted collaborators sees, but sort of like a wiki, in that everything can be edited after the fact by anyone else (with the old versions still viewable)? And while we're at it, why not make this system sort of like a threaded web forum where one can share a whole long thread with additional people long after it starts, and sort of like an outliner that lets you build a hierarchical structure for your ideas, and maybe also sort of like a chat system where one can see what everyone else in the same thread is typing as they type it? And even sort of like LaTeX^* in that it knows how to format equations and not just the usual text and pictures?

That's what Google Wave is.

I've been using Wave for all of a week now for one of my papers and I already regret the times I lapsed back into my old bad habits to work on it by email. I'm not giving up on email any time soon but for some situations there are other tools that are better, and I think this is one of those situations. Wave is in beta (justifiably so: the server is...robust) and still invitation-only. But apparently a week is long enough for me to be an old hand^** and start inviting a few other people to join me, so if you want an invite and somehow haven't managed to score one already elsewhere then feel free to ask here.

^*Ok, the LaTeX part isn't there by default. It's an extra gadget that you have to add on, but it's easy to do so. I haven't used it much, though: most of the time when I need math it's just for simple formulas like O(n²) that are easy enough to type inline.

^**If I'm an old hand, then Suresh and Lance are ancient and decrepit and over-the-hill.

Update: all eight of my initial set of invitations are used now but bhael has more; see the comments.

If I haven't been posting much here in the last couple of weeks, it's because too much of my writing energy has been going into writing actual papers. Here's one of them: Growth and Decay in Life-Like Cellular Automata, arXiv:0911.2890. The aim of the paper is to predict which two-dimensional cellular automaton rules will behave similarly to Conway's Game of Life. But a large part of the difficulty in making this sort of prediction is finding the right definition of "similarly".

( Read more... )

My photos from Halloween are now online. Pumpkin picking, carved pumpkins, my son and his friend in costume, that sort of thing.

As a follow-up to the problem of coloring triangle-free line segment intersection graphs that I posted the other day, here's another line segment intersection representation of the Grötzsch graph. This time I drew it with only four different slopes of line segments, making it obvious that it can be 4-colored (just use a different color for each slope). And conversely the fact that this graph requires four colors implies that I couldn't have drawn it with fewer than four slopes. Is there a bound on the number of distinct slopes needed to realize all triangle-free line segment intersection graphs? It seems likely to be hard to prove that this number is bounded, if it is, since that would also solve the coloring problem. But maybe it's easy to come up with a family of triangle-free line segment intersection graphs that require an unbounded number of slopes?



A natural candidate for an (infinite) line segment intersection graph requiring an unbounded number of slopes is the order-4 pentagonal tiling of the hyperbolic plane, the Klein model of which forms a triangle-free line segment arrangement in the Euclidean plane. But I don't see an easy way to get a handle on how many slopes it needs.

Via Mike Trick's twitter feed I learn of a case of plagiarism published on SIAM's web site. Most of the papers that were plagiarized seem to be in operations research, but one of them is computational geometry: one of the victimized authors is Godfried Toussaint, whose paper (copied by the plagiarists) concerns a one-dimensional geometric matching problem for testing how similar two point sets are that is somewhat related to the calculation of Haussdorff distance.

To me the most interesting part of the story is the lack of response from the journals and universities associated with the plagiarists. Do they hope to avoid publicity by keeping the story quiet? But by failing to respond they have prompted SIAM to take this public step, and made themselves look like collaborators in the plagiarism.

I spent the last week visiting the Institute for Pure and Applied Mathematics at UCLA, for a workshop on combinatorial geometry. Rather than post here about the many exciting new results I heard about (for which see the conference program) I thought I'd describe a few open problems that came up in some of the talks.

( Coloring line segments )

( Blocking visibilities among points )

( Counting spanning trees in bipartite graphs )

( Triple crossings of unit circles )

Aesthetics of commutative diagrams. An interesting discussion of graph drawing in the context of graphs that represent mathematical formulas. Does one lay them out in a nice grid pattern which makes the formulas easier to read, or does one choose a less uniform vertex placement in which the global shape of the diagram (its outside face) conveys the intended meaning of the diagram?

The graph drawn above is the planar dual to the Herschel graph. The Herschel graph has nine quadrilateral faces, so its dual is a 9-vertex 4-regular planar graph, and therefore can be drawn as the arrangement graph of a system of smooth curves, or as in this case as the self-crossings of a single smooth curve.

Much of the research in graph drawing uses a drawing style in which edges are drawn as straight line segments, or as sequences of straight line segments articulated by "bends", corners where two line segments meet. But I think that, in many cases, smooth curves can create a more interesting aesthetic effect, that the extra freedom inherent in drawing curves makes it possible to spread out the features of the drawing more evenly, and that smooth curves are likely to be easier for the eye to follow than sharp bends.

No doubt Mark Lombardi would agree.

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... )

In conjunction with Bill Gasarch's call for including as many links as possible in the bibliographies of our papers (and for us to take some other more important steps towards open access; see also here) I've updated a BibTeX style file, abuser.bst, that I've been using in conjunction with pdflatex and the url package hyperref package in order to make hyperlinks in my papers' bibliographies.

Basically, you use this package very much like the standard BibTeX abbrv style, with the following changes:

• For book series, such as LNCS, it is preferable to use number={nnnn} rather than volume={nnnn} to indicate the number of the book within the series; this frees the volume to indicate the volume of a multivolume work (which might exist within a differently numbered series). The formatting is also a little more compact; e.g. series={LNCS}, number={1234} produces "LNCS 1234" rather than "vol. 1234, other information, LNCS".


• url={...} includes the given url within the formatted reference, as a hyperlink for TeX systems that support hyperlinking.


• eprint={...} includes the arxiv paper with the given eprint number, as a hyperlink for TeX systems that support hyperlinking.


• doi={...} includes the given doi, as a hyperlink for TeX systems that support hyperlinking. If you're not familiar with the doi system, it's a way to provide links to the publisher's web site for journal and conference papers that is supposedly more permanent than just using a url (as publishers often change their url schema but are not supposed to change their dois). So this doesn't do anything about the open access issue but does allow easy hyperlinking of online published content. The doi is usually included somewhere on the publisher's web page for an article but can also be looked up using crossref.org.


• There's a note at the top of the file about Dutch names being sorted correctly (that is, "van Kreveld" should be sorted under "K"), but I no longer remember what I did to achieve this.

If you need something other than abbrv, you're on your own, but I hope this is helpful to at least a few other people than myself.

I just finished uploading five new sets of photos:

• Mathematical sculpture at Trinity College Dublin. Or sort-of mathematical: the artist may have intended one of these sculptures to model DNA, but to a topologist it looks like a torus link. Apparently every year the Hamilton Workshop on Geometry and Topology uses one of these as a logo, but they're running out: soon they'll have to go with the kitschy sculpture of a buxom Molly Malone outside the college gate.


• Dublin. Or the parts of it that I saw outside of Trinity and Guinness. With my usual complement of graffiti.


• The Guinness Storehouse. Supposedly Ireland's biggest tourist attraction. I didn't take many photos inside, although I found the tour quite interesting; most of the photos are of the 360-degree view of the Guinness brewery that one gets from the bar at the top of the tour.


• Chicago. The weather was not really conducive to photography but I took a couple of shots anyway.


• Graph Drawing 2009. If you didn't go, now's your chance to see what you missed. If you did go, you can see how many photos you and your friends are in. I hope none of the ones I kept are too embarrassing or unflattering. ETA: The GD09 web site now also links to another set of photos by Pranava Jha.

After two conferences I'm too tired to successfully post anything serious. So, since Graph Drawing lacks a public business meeting at which to present these, here instead are some statistics on acceptances and rejections at the conference.

( Read more... )

Two of the papers presented today at Graph Drawing (and one earlier at WADS) concerned drawings in which edges that cross are required to do so at a high angle. One of today's papers ("On the perspectives opened by right angle crossing drawings", by Angelini et al) included some results on bounded degree graphs, showing that graphs with sufficiently low degree bounds could be given drawings with right-angled crossings and few bends per edge. The other paper ("Area, curve complexity, and crossing resolution of non-planar graph drawings", by Di Giacomo et al) generalized the problem, looking not just at right angled drawings but at drawings in which all crossings have an angle bounded away from zero; the "crossing resolution" of the title is the minimum angle of any crossing. So what if we put both of these together and look at the crossing resolution of bounded-degree graphs?

( Read more... )

ETA: János Pach points out that the same relation between geometric thickness and crossing resolution allows one to prove an O(1/n) bound on the crossing resolution of n-vertex complete graphs from known results on geometric thickness of complete graphs, improving a logarithmic bound from the Di Giacomo et al paper and an O(1/√n) bound obtained from a result of Aronov et al. that any n points in general position have Ω(√n) pairwise crossing line segments.

I've been visiting Dublin, Ireland (my first time here) for the Fifth William Rowan Hamilton Geometry and Topology Workshop at the Hamilton Mathematics Institute of Trinity College, where I spoke about hyperconvex metric spaces, finding optimal stars, orthogonal convex hulls, and embedding into the Manhattan plane.

It was a good conference, but a bit like stepping into a parallel world where everyone's evil twin does low-dimensional topology and geometric group theory: the workshop theme had the phrase "Computational Geometry" in it, but it's an Other Computational Geometry that really mostly means low-dimensional topology and geometric group theory; there's an Other David Epstein (spelled wrong) who does etc and was here last year; and there's an Other Kevin Wortman (not spelled wrong) who does etc and wasn't here, but whose name caused some confusion when I referred to the work of my former student Kevin Wortman. Still, my interests and those of the Other Computational Geometers have enough overlap that I think we all got something useful out of the experience.

I'm not going to recount all of the talks (especially because I didn't understand them all) but here are a few that caught my attention.

( Read more... )

The orthogonal polyhedron shown below has an interesting combination of properties: it is orthogonally convex (any axis-parallel line intersects it in a point, an interval, or the empty set) but not simply-connected.



My first thought on completing this drawing was: its skeleton is a highly symmetric cubic torus graph with 24 vertices...must be the Nauru graph! But it isn't. It's vertex-transitive but, unlike the Nauru graph, not edge-transitive: the edges that wrap the short way around the torus each belong to only two six-cycles (the two faces on either side of the edge) but the edges that wrap the long way around belong to three (the two faces and their equatorial cycle).

As promised, I've finally put up Diana's photos from Banff, complete with grizzle bear.

Much of the delay was due to a chain of reinstallations of software and libraries I needed to perform to get my web photo gallery software working again after upgrading to Snow Leopard. Why doesn't software just work? (Asks the computer scientist, who should know better.)

To go along with her newly minted assistant professorship at Oregon State University, Cora Borradaile has started a new blog, Silent Glen Speaks. So far there's only an introductory post (and, on the RSS feed, some abstracts of older papers) but I'll be watching for more. Welcome to the blogosphere, Cora!

I just uploaded two new papers to the arXiv, and my co-author updated an old one:

Optimally fast incremental Manhattan plane embedding and planar tight span construction, arXiv:0909.1866. The concrete problem solved here is testing whether a finite metric space can be represented as the distances among a set of points in the Manhattan plane. The corresponding Euclidean problem is easy (find a non-collinear triple of points, place them in a triangle, and use them to determine uniquely the Euclidean location of the remaining points) but the best previous problem for the Manhattan-metric variant took O(n²log²n) time; this paper removes the logs, getting the time bound down to the size of the input distance matrix, using the tight span as a key tool. The tight span is an analogue for finite metric spaces of the convex hull for finite Euclidean point sets. In general it can be computed as the set of bounded faces of a high-dimensional polytope, but that's not very efficient. The main ideas of the paper are to provide a different method of representing and constructing tight spans that are homeomorphic to a subset of the plane, using rectangular complexes and Manhattan orbifolds.

Paired approximation problems and incompatible inapproximabilities, arXiv:0909.1870. To appear at SODA. If two different approximation problems are defined from the same input and you'd be satisfied with a solution to either, it turns out that the quality of approximation you get can be significantly better than for either problem alone. For instance, suppose you want either a coloring or a long path in a graph. Both problems are hard to approximate to within a significantly sublinear approximation ratio (although we don't know how to prove it for the path problem) but approximating one or the other to within √n is easy using depth-first search: if the DFS tree has many levels it contains a long path, and otherwise the partition into levels is a good coloring. Along with several similar examples the paper contains some other pairs of problems (such as set cover and hitting set) where it's not possible to get a better approximation than for either problem alone; that part ws less easy.

Straggler identification in round-trip data streams via Newton's identities and invertible Bloom filters, arXiv:0704.3313. Now updated with some experimental results for the Bloom filter data structure as requested by the referees, I think primarily as a proof-of-concept to show that the algorithms are implementable. When we first did these experiments we thought we saw some interesting phenomena in them, showing that some complications that we'd included for theoretical reasons (we couldn't figure out how to prove that it worked without them) were also necessary to achieve good practical performance. Sadly, that turned out to be a bug in our implementation. But at least the debugged experiments still show that the extra space used for the added part of the data structure is not wasted: it gives us a proportionate increase in the size of the sets we can identify.

Connect the corners of six unit equilateral triangles by hinges in the pattern shown below (so that the graph formed by the edges and hinges is the Cartesian product of two triangles).



The resulting linkage system of triangles and hinges has (up to symmetry of the plane) a single degree of freedom: if we add a single bar restricting the distance between two hinges on one of the axes of symmetry of the system, it becomes rigid. Therefore, as it flexes, the hinges will remain in a pattern like the one shown, in which they are arranged to form three more concentric equilateral triangles of varying sizes.

It's possible for at least two of these variable-sized equilateral triangles to have side lengths that are rational numbers. For instance, in the illustration above, the triangles and hinges were placed in such a way that the triangle formed by the three innermost hinges has side length 2/7, and the triangle formed by the three outermost hinges has side length 13/7. What about the middle triangle? Is it rational? In general, can all three of these nested triangles be rational?

Yes and yes. It's possible to show this by manipulating formulas for the length (I had this all worked out, starting from some trigonometric formulas in terms of the angles of the hinges and converting them into complex number arithmetic), but there's a much simpler geometric demonstration. Look at the figure above, which is arranged to have a vertical axis of symmetry. Suppose that the side length of the largest equilateral triangle is a rational number q, and the side length of the smallest equilateral triangle is a rational number r. Place the figure so that the axis of symmetry lies on the y-axis of the plane. Then the leftmost and rightmost vertices have x-coordinates −q/2 and q/2, respectively. Similarly the left and right vertices of the inner triangle have x-coordinates −r/2 and r/2, respectively. The left and right vertices of the middle triangle are connected to the leftmost and rightmost vertices by edges that are translates of edges from the bottom vertex (on the center line) to the left and right inner vertices; therefore the x-coordinates of the middle triangle are −q/2 + r/2 and q/2 − r/2, and the side length of the middle triangle is q − r. If q and r are both rational, so is their difference. In the case of the configuration shown in the drawing, the middle length is 11/7.

In general there are infinitely many angles for which all three nested triangles have rational side length, dense in the set of all such angles. The technique for generating them resembles that for generating Pythagorean triples.

Incidentally, there's a four-dimensional convex polytope (the Cartesian product of two equilateral triangles) that has this same graph as its skeleton. It has six triangular 2-faces, nine square 2-faces, and six triangular-prism facets. Can you see them all in the drawing above?

ETA: Konrad Swanepoel uses a similar arrangement of Reuleaux triangles to show that three nonoverlapping translates of a convex body can overlap three nonoverlapping 180-degree rotations of the same body.