This Wednesday's deadline for the final proceedings version of papers for Graph Drawing 2013 must be drawing near: tonight's update to arXiv.org includes seven new preprints on graph drawing. They are:

Transforming planar graph drawings while maintaining height

arXiv:1308.6693, Therese Biedl. The question Therese considers is under what circumstances one can change the style of a drawing (e.g. from having straight edges to having edges that bend but must remain axis-parallel) while preserving its overall dimensions. This is a follow-on to a previous paper by Biedl from GD 2009 that briefly discussed similar transformations in the context of finding area-efficient drawings of certain graph classes.

Drawings of non-planar graphs with crossing-free subgraphs

arXiv:1308.6706, Patrizio Angelini, Carla Binucci, Giordano Da Lozzo, Walter Didimo, Luca Grilli, Fabrizio Montecchiani, Maurizio Patrignani, and Ioannis G. Tollis. If you're given a graph in which some edges are allowed to participate in crossings while others must remain uncrossed, how can you draw it, respecting these constraints? Unfortunately the authors were unable to determine the computational complexity of this problem, and leave it as an interesting open problem. Instead they show that certain special cases when the uncrossable edges form a spanning tree always have good drawings.

Streamed graph drawing and the file maintenance problem

arXiv:1308.6711, Michael T. Goodrich and Paweł Pszona. The file maintenance problem is to number the elements of a changing ordered set, in an order-preserving way, by integers whose magnitude is proportional to the size of the set. Some elements will have to be renumbered but you want to keep renumberings infrequent. They apply this to maintaining high-quality drawings of changing graphs. Earlier work on this problem didn't allow previously-drawn features to move at all, as a consequence of which the drawings were quite bad (e.g. exponential in area), but Goodrich and Pszona show that by redrawing only a small subset of the graph after each update, the quality can be made much higher.

Achieving good angular resolution in 3D arc diagrams

arXiv:1308.6730, Michael T. Goodrich and Paweł Pszona. A well-known paper in InfoVis 1996 by GD13 invited speaker Tamara Munzner, "Visualizing the global topology of the MBone", drew a telecommunications network on a globe, with its links shown as arcs looping up away from the Earth and back down. But there is a lot of freedom of choice in how to draw each arc: does it fly over a great circle route between its endpoints or does it lie in a tilted plane? What angle does it make when it leaves and returns to the Earth's surface? This paper uses graph coloring to make those choices in a way that avoids sharp angles between arcs with the same endpoints.

Using ILP/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings

arXiv:1308.6778, Therese Biedl, Thomas Bläsius, Benjamin Niedermann, Martin Nöllenburg, Roman Prutkin, and Ignaz Rutter. This paper is in a line of research started (I think) by Healy and Nikolov in GD 2001 and continued by Chimani, Gutwenger, Mutzel, and Bomze at ISAAC 2007 and ESA 2008 of solving NP-hard graph drawing problems exactly, without guaranteed bounds on the running time, by setting up integer linear programs to solve them. It's a reasonable thing to do because the graphs to be drawn are often not large — otherwise the drawing couldn't be readable — so these approaches can finish in a practical amount of time despite their exponentiality.

Many-to-one boundary labeling with backbones

arXiv:1308.6801, Michael A. Bekos, Sabine Cornelsen, Martin Fink, Seokhee Hong, Michael Kaufmann, Martin Nöllenburg, Ignaz Rutter, and Antonios Symvonis. There have been quite a few papers lately on problems like the one studied here, in which one must place labels around the boundary of a map and draw connecting lines from them to the features they label. Here's the first example of this drawing style that I found in a Google image search. I'm not at all convinced that the approach taken by most of these papers, of using axis-parallel connectors with bends, is a good idea: straight lines at arbitrary angles (as in the example) seem likely to be both less confusing and easier to route away from the map features that shouldn't be obscured. But be that as it may, the version of the problem here involves labels that describe sets of mutiple objects, and connectors in the form of a caterpillar tree with one horizontal spine and many vertical leaf edges.

Strict confluent drawing

arXiv:1308.6824, by David Eppstein, Danny Holten, Maarten Löffler, Martin Nöllenburg, Bettina Speckmann, and Kevin Verbeek. A confluent drawing envisions a graph as a system of curved train tracks with junctions (on which the edges are routed) and stations (the vertices). Two vertices are connected by an edge whenever there exists a smooth route via tracks and junctions from station to station. This style can greatly declutter graph drawings — a good example is here, simplifying a graph that my co-authors and I had drawn more complicatedly, winning the GD 2011 contest. This paper constrains these drawings by disallowing multiple routes between the same two stations; as well as making them less confusing to read, this helps clarify their computational complexity. The constrained drawings always have linearly many features (unlike some previous results in this area), and can be constructed in polynomial time when the stations are all in fixed locations on the sea-coast of their continent, but are NP-complete to find in general.