Track 1: Combinatorial and algorithmic aspects

• Md. Jawaherul Alam and Stephen G. Kobourov
  Proportional Contact Representations of 4-connected Planar Graphs [+]

  In a contact representation of a planar graph, vertices are represented by interior-disjoint polygons and two polygons share a non-empty common boundary when the corresponding vertices are adjacent. In the weighted version, a weight is assigned to each vertex and a contact representation is called proportional if each polygon realizes an area proportional to the vertex weight. In this paper we study proportional contact representations of 4-connected internally triangulated planar graphs. The best known lower and upper bounds on the polygonal complexity for such graphs are 4 and 8, respectively. We narrow the gap between them by proving the existence of a representation with complexity 6. We then disprove a 10-year old conjecture on the existence of a Hamiltonian canonical cycle in a 4-connected maximal planar graph, which also implies that a previously suggested method for constructing proportional contact representations of complexity 6 for these graphs will not work. Finally we prove that it is {\bf NP}-complete to decide whether a 4-connected planar graph admits a contact representation using only rectangles.

• Soroush Alamdari and Therese Biedl
  Open Rectangle-of-Influence Drawings of Non-Triangulated Planar Graphs [+]

  A straight line drawing of a graph is an open weak rectangle- of-influence (RI) drawing if there is no vertex in the relative interior of the axis parallel rectangle induced by the end points of each edge. Despite recent interest of the graph drawing community in rectangle-of-influence drawings, no algorithm is known to test whether a graph has a planar open weak RI-drawing. In a recent paper, we showed how to test, for inner-triangulated planar graphs, whether they have a planar open weak RI-drawing with a non- aligned frame, i.e., the graph obtained from removing the interior of every filled triangle is drawn such that no two vertices have the same coordinate. In this paper, we generalize this to all planar graphs with a fixed planar embedding, even if some interior faces are not triangles. On the other hand, we show that if the planar embedding is not fixed, then deciding if a given planar graph has an open weak RI-drawing is NP-complete. NP-completeness holds even for open weak RI-drawings with non-aligned frames.

• Soroush Alamdari, Timothy M. Chan, Elyot Grant, Anna Lubiw and Vinayak Pathak
  Self-Approaching Graphs [+]

  In this paper we introduce self-approaching graph drawings. A straight-line drawing of a graph is self-approaching if, for any origin vertex $s$ and any destination vertex $t$, there is an $st$-path in the graph such that, for any point $q$ on the path, as a point $p$ moves continuously along the path from the origin to $q$, the Euclidean distance from $p$ to $q$ is always decreasing. This is a more stringent condition than a greedy drawing (where only the distance between vertices on the path and the destination vertex must decrease), and guarantees that the drawing is a 5.33-spanner. We study three topics: (1) recognizing self-approaching drawings; (2) constructing self-approaching drawings of a given graph; (3) constructing a self-approaching Steiner network connecting a given set of points. We show that: (1) there are efficient algorithms to test if a polygonal path is self-approaching in R^2 and R^3, but it is NP-hard to test if a given graph drawing in R^3 has a self-approaching $uv$-path; (2) we can characterize the trees that have self-approaching drawings; (3) for any given set of terminal points in the plane, we can find a linear sized network that has a self-approaching path between any ordered pair of terminals.

• Patrizio Angelini, Marco Di Bartolomeo and Giuseppe Di Battista
  Implementing a Partitioned $2$-page Book Embedding Testing Algorithm [+]

  In a book embedding the vertices of a graph are placed on the ``spine'' of a ``book'' and the edges are assigned to ``pages'' so that edges on the same page do not cross. In the \belong problem the egdes are partitioned into two sets $E_1$ and $E_2$, the pages are two, the edges of $E_1$ are pre-assigned to page $1$, and the edges of $E_2$ are pre-assigned to page $2$. The problem consists of checking if an ordering of the vertices exists along the spine so that the edges of each page do not cross. Hong and Nagamochi~\cite{hn-tpbesg-09tr} give an interesting and complex linear time algorithm for tackling \belong based on SPQR-trees. We show an efficient implementation of this algorithm and show its effectiveness by performing a number of experimental tests. Because of the relationships between \belong and clustered planarity we yield as a side effect an implementation of a clustered planarity testing where the graph has exactly two clusters.

• Martin Balko
  Grid Drawings and the Chromatic Number [+]

  A grid drawing of a graph maps vertices to the $d$-dimensional grid and edges to line segments that avoid grid points representing other vertices. We show that a graph $G$ is $q^{d}$-colorable, $d$, $q \geq 2$, if and only if there is a grid drawing of $G$ in the $d$-dimensional grid in which no line segment intersects more than $q$ grid points. This strengthens the result of D.~Flores Pe\H{n}aloza and F.~J.~Zaragoza Martinez. Second, we study grid drawings with bounded number of columns, introducing some new $\NP$-complete problems. We also show a sharp lower bound on the area of plane grid drawings of balanced complete $k$-partite graphs, proving a conjecture of David~R.~Wood. Finally, we show that any planar graph has a planar grid drawing where every line segment contains exactly two grid points. This result proves conjectures asked by D.~Flores Pe\H{n}aloza and F.~J.~Zaragoza Martinez.

• Michael Bekos and Chrysanthi Raftopoulou
  Circle-Representations of Simple 4-Regular Planar Graphs [+]

  Lov\'asz conjectured that every connected 4-regular planar graph $G$ admits a \emph{realization as a system of circles}, i.e., it can be drawn on the plane utilizing a set of circles, such that the vertices of $G$ correspond to the intersection and touching points of the circles and the edges of $G$ are the arc segments among pairs of intersection and touching points of the circles. In this paper, we settle this conjecture. In particular, (a)~we affirmatively answer Lov\'asz's conjecture, if $G$ is 3-connected, and, (b)~we demonstrate an infinite class of connected 4-regular planar graphs which are not 3-connected and do not admit a realization as a system of circles.

• Michael Bekos, Stephen Kobourov, Michael Kaufmann and Antonios Symvonis
  Smooth Orthogonal Layouts [+]

  We study the problem of creating {\em smooth orthogonal layouts} for planar graphs. While in traditional orthogonal layouts every edge is made of a sequence of axis-aligned line segments, in smooth orthogonal layouts every edge is made of axis-aligned segments and circular arcs with common tangents. Our goal is to create such layouts with low edge complexity, measured by the number of line and circular arc segments. We show that every biconnected 4-planar graph has a smooth orthogonal layout with edge complexity 3. If the input graph has a complexity-2 traditional orthogonal layout we can transform it into a smooth complexity-2 layout. Using the Kandinsky model for removing the degree restriction, we show that any planar graph has a smooth complexity-2 layout.

• Gregor Betz, Christof Doll, Andreas Gemsa, Ignaz Rutter and Dorothea Wagner
  Column-based Graph Layouts [+]

  We consider orthogonal upward drawings of directed acyclic graphs (DAGs) with nodes of uniform width but node-specific height. One way to draw such graphs is to use a layering technique as provided by the Sugiyama Framework. However, to avoid drawbacks of the Sugiyama Framework we use the layer-free upward crossing minimization algorithm suggested by Chimani et al. and integrate it into the topology-shape-metric (TSM) framework introduced by Tamassia. This in combination with an algorithm by Biedl and Kant lets us generate column-based layouts, i.e., layouts where the plane is divided into uniform-width columns and every node is assigned to a column. We show that our column-based approach allow to generate visually appealing, compact layouts with with few edge crossing, at most four bends per edge. Furthermore, the resulting layouts exhibit a high degree of symmetry and implicitly support edge bundling. We justify our approach by an experimental evaluation based on real-world examples.

• Thomas Bläsius and Ignaz Rutter
  Disconnectivity and Relative Positions in Simultaneous Embeddings [+]

  For two planar graph $\1G = (\1V, \1E)$ and $\2G = (\2V, \2E)$ sharing a common subgraph $G = \1G \cap \2G$ the problem {\sc Simultaneous Embedding with Fixed Edges (SEFE)} asks whether they admit planar drawings such that the common graph is drawn the same. Previous algorithms only work for cases where~$G$ is connected, and hence do not need to handle relative positions of connected components. We consider the problem where~$G$, $\1G$ and~$\2G$ are not necessarily connected. First, we show that a general instance of {\sc SEFE} can be reduced in linear time to an equivalent instance where $\1V = \2V$ and $\1G$ and $\2G$ are connected. Second, for the case where~$G$ consists of disjoint cycles, we introduce the \emph{CC-tree} representing all embeddings of~$G$ that extend to planar embeddings of~$\1G$. We show that CC-trees can be computed in linear time, and that their intersection is again a CC-tree. This yields a linear-time algorithm for {\sc SEFE} if all input graphs share the same set of disjoint cycles. These results, including the CC-tree, extend to the case where $G$ consists of arbitrary connected components, each with a fixed embedding. In this case the running time is~$O(n^2)$.

• Franz Josef Brandenburg, David Eppstein, Andreas Gleißner, Michael T. Goodrich, Kathrin Hanauer and Josef Reislhuber
  On the Density of Maximal 1-Planar Graphs [+]

  A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. It is maximal 1-planar if the addition of any edge violates 1-planarity. Maximal 1-planar graphs have at most 4 n - 8 edges. We show that there are sparse maximal 1-planar graphs with only 45/17 n + O(1) edges. With a fixed rotation system there are maximal 1-planar graphs with only 7/3 n + O(1) edges, which is sparser than maximal planar graphs. There cannot be maximal 1-planar graphs with less than 21/10 n - O(1) edges and less than 28/13 n - O(1) edges with a fixed rotation system. Furthermore, we prove that a maximal 1-planar rotation system of a graph uniquely determines its 1-planar embedding.

• David Bremner, Will Evans, Fabrizio Frati, Laurie Heyer, Stephen Kobourov, William Lenhart, Giuseppe Liotta, David Rappaport and Sue Whitesides
  On Representing Graphs by Touching Cuboids [+]

  We consider contact representations of graphs where vertices are represented by cuboids, i.e. interior-disjoint axis-aligned boxes in 3D space. Edges are represented by a proper contact between the cuboids representing their endvertices. Two cuboids make a proper contact if they intersect and their intersection is a non-zero area rectangle contained in the boundary of both. We study representations where all cuboids are unit cubes, where they are cubes of different sizes, and where they are axis-aligned 3D boxes. We prove that it is NP-complete to decide whether a graph admits a proper contact representation by unit cubes. We also describe algorithms that compute proper contact representations of varying size cubes for relevant graph families. Finally, we give two new simple proofs of a theorem by Thomassen stating that all planar graphs have a proper contact representation by touching cuboids.

• Till Bruckdorfer, Sabine Cornelsen, Carsten Gutwenger, Michael Kaufmann, Fabrizio Montecchiani, Martin Nöllenburg and Alexander Wolff
  Progress on Partial Edge Drawings [+]

  Recently, a new way of avoiding crossings in straight-line drawings of non-planar graphs has been investigated. The idea of \emph{partial edge drawings} (PED) is to drop the middle part of edges and rely on the remaining edge parts called \emph{stubs}. We focus on a symmetric model (SPED) that requires the two stubs of an edge to be of equal length. In this way, the stub at the other endpoint of an edge assures the viewer of the edge's existence. We also consider an additional homogeneity constraint that forces the stub lengths to be a given fraction~$\delta$ of the edge lengths ($\delta$-SHPED). Given length and direction of a stub, this model helps to infer the position of the opposite stub. We show that, for a fixed stub--edge length ratio~$\delta$, not all graphs have a $\delta$-SHPED. Specifically, we show that $K_{183}$ does not have a $1/4$-SHPED, while bandwidth-$k$ graphs always have a $\Theta(1/\sqrt{k})$-SHPED. We also give bounds for complete bipartite graphs. Further, we consider the problem \textsc{MaxSPED} where the task is to compute the SPED of maximum total stub length that a given straight-line drawing contains. We present an efficient solution for 2-planar drawings and a 2-approximation algorithm for the dual problem.

• Luca Castelli Aleardi, Olivier Devillers and Eric Fusy
  Canonical ordering for triangulations on the cylinder, with applications to periodic straight-line drawings [+]

  We extend the notion of canonical orderings to cylindric triangulations. This allows us to extend the incremental straight-line drawing algorithm of de Fraysseix et al. to this setting. Our algorithm yields in linear time a crossing-free straight-line drawing of a cylindric triangulation $T$ with $n$ vertices on a regular grid $Z/wZ\times[0,h]$, with $w\leq 2n$ and $h\leq n(2d+1)$, where $d$ is the (graph-) distance between the two boundaries. As a by-product, we can also obtain in linear time a crossing-free straight-line drawing of a toroidal triangulation with $n$ vertices on a periodic regular grid $Z/wZ\times Z/hZ$, with $w\leq 2n$ and $h\leq 1+n(2c+1)$, where $c$ is the length of a shortest non-contractible cycle. Since $c\leq\sqrt{2n}$, the grid area is $O(n^{5/2})$.

• Steven Chaplick and Torsten Ueckerdt
  Planar Graphs as VPG-Graphs [+]

  A graph is $B_k$-VPG when it has an intersection representation by paths in a rectangular grid with at most $k$ bends (turns). It is known that all planar graphs are contained in $B_3$-VPG and this was conjectured to be tight. We disprove this conjecture by showing that all planar graphs are contained in $B_2$-VPG. We also show that the 4-connected planar graphs are a subclass of the intersection graphs of $Z$-shapes (i.e., a special subclass of $B_2$-VPG). Additionally, we demonstrate that a $B_2$-VPG representation of a planar graph can be constructed in $O(n^{3/2})$ time. We further show that the triangle-free planar graphs are contact graphs of: L-shapes, \G-shapes, vertical segments, and horizontal segments (i.e., a special case of contact $B_1$-VPG). From this proof we gain a new proof that bipartite planar graphs are a subclass of 2-DIR.

• Markus Chimani and Robert Zeranski
  Upward Planarity via SAT [+]

  A directed acyclic graph is \emph{upward planar} if it allows a drawing without edge crossings where all edges are drawn as curves with monotonously increasing $y$-coordinates. The problem to decide whether a graph is upward planar or not is NP-complete in general, and while special graph classes are polynomial time solvable, there is not much known about solving the problem for general graphs \emph{in practice}. The only attempt so far was a branch-and-bound algorithm over the graph's triconnectivity structure which was able to solve sparse graphs. In this paper, we propose a fundamentally different approach, based on the seemingly novel concept of \emph{ordered embeddings}. We carefully model the problem as a special \Sat instance, i.e., a logic formula for which we check satisfiability. Solving these \Sat instances, allows us to decide upward planarity for arbitrary graphs. We then show experimentally that this approach dominates the known alternative approaches and is able to solve traditionally used graph drawing instances effectively.

• Emilio Di Giacomo, Giuseppe Liotta and Henk Meijer
  The Approximate Rectangle of Influence Drawability Problem [+]

  We prove that all planar graphs have an open/closed $(\epsilon_1,\epsilon_2)$-rectangle of influence drawing for $\epsilon_1 >0$ and $\epsilon_2 >0$, while there are planar graphs which do not admit an open/closed $(\epsilon_1,0)$-rectangle of influence drawing and planar graphs which do not admit a $(0,\epsilon_2)$-rectangle of influence drawing. We then show that all outerplanar graphs have an open/closed $(0,\epsilon_2)$-rectangle of influence drawing for any $\epsilon_2 \geq 0$. We also prove that if $\epsilon_2 > 2$ an open/closed $(0, \epsilon_2)$-rectangle of influence drawing of an outerplanar graph can be computed in polynomial area. For values of $\epsilon_2$ such that $\epsilon_2 \leq 2$, we describe a drawing algorithm that computes $(0,\epsilon_2)$-rectangle of influence drawings of binary trees in area $O(n^{2 + f(\epsilon_2)})$, where $f(\epsilon_2)$ is a logarithmic function that tends to infinity as $\epsilon_2$ tends to zero, and $n$ is the number of vertices of the input tree.

• Adrian Dumitrescu and Csaba Toth
  Covering paths for planar point sets [+]

  Given a set of points, a \emph{covering path} is a directed polygonal path that visits all the points. We show that for any $n$ points in the plane, there exists a (possibly self-crossing) covering path consisting of $n/2 +O(n/\log{n})$ straight line segments. If no three points are collinear, any covering path (self-crossing or non-crossing) needs at least $n/2$ segments. If the path is required to be non-crossing, $n-1$ straight line segments obviously suffice and we exhibit $n$-element point sets in general position which require at least $5n/9 -O(1)$ segments in any such path. Further, we show that computing a non-crossing covering path for $n$ points in the plane requires $\Omega(n \log{n})$ time in the worst case.

• Peter Eades, Seok-Hee Hong, Naoki Katoh, Giuseppe Liotta, Pascal Schweitzer and Yusuke Suzuki
  Testing Maximal 1-planarity of Graphs with a Rotation System in Linear Time [+]

  A {\em 1-planar} graph is a graph that can be embedded in the plane with at most one crossing per edge. A 1-planar graph on~$n$ vertices can have at most $4n-8$ edges. It is known that testing 1-planarity of a graph is NP-complete. A 1-planar embedding of a graph $G$ is {\em maximal}, if no edge can be added without violating the 1-planarity of $G$. In this paper, we study combinatorial properties of maximal 1-planar embeddings. In particular, we show that in a maximal 1-planar embedding, the graph induced by the non-crossing edges is spanning and biconnected. Using the properties, we show that the problem of testing maximal 1-planarity of a graph $G$ can be solved in linear time, if a {\em rotation system} $\Phi$ (i.e., the circular ordering of edges for each vertex) is given. We also prove that there is at most one maximal 1-planar embedding $\xi$ of $G$ that preserves the given rotation system $\Phi$, and our algorithm also produces such an embedding in linear time, if it exists. In addition, we establish new bounds on the minimum number of edges of maximal 1-plane graphs, showing that for graphs on~$n$ vertices this number is between~$\frac{9n}{5}-\frac{18}{5}$ and~$\frac{7n}{3} -2$.

• David Eppstein
  Planar Lombardi Drawings for Subcubic Graphs [+]

  We prove that every planar graph with maximum degree three has a planar drawing in which the edges are drawn as circular arcs that meet at equal angles around every vertex. Our construction is based on the Koebe–Thurston–Andreev circle packing theorem, and uses a novel type of Voronoi diagram for circle packings that is invariant under Möbius transformations, defined using three-dimensional hyperbolic geometry. We also use circle packing to construct planar Lombardi drawings of a special class of 4-regular planar graphs, the medial graphs of polyhedral graphs, and we show that not every 4-regular planar graph has a Lombardi drawing. We have implemented our algorithm for 3-connected planar cubic graphs.

• Fabrizio Frati, Marc Glisse, William Lenhart, Giuseppe Liotta, Tamara Mchedlidze and Rahnuma Islam Nishat
  Point-Set Embeddability of 2-Colored Trees [+]

  In this paper we study bichromatic point-set embeddings of $2$-colored trees on $2$-colored point sets, i.e., point-set embeddings of trees (whose vertices are colored red and blue) on point sets (whose points are colored red and blue) such that each red (blue) vertex is mapped to a red (resp. blue) point. We prove that deciding whether a given $2$-colored tree admits a bichromatic point-set embedding on a given convex point set is an $\cal NP$-complete problem; we also show that the same problem is linear-time solvable if the convex point set does not contain two consecutive points with the same color. Furthermore, we prove a $3n/2-O(1)$ lower bound and a $2n$ upper bound (a $7n/6-O(\log n)$ lower bound and a $4n/3$ upper bound) on the minimum size of a universal point set for straight-line bichromatic embeddings of $2$-colored trees (resp. $2$-colored binary trees). Finally, we show that universal convex point sets with $n$ points exist for $1$-bend bichromatic point-set embeddings of $2$-colored trees.

• Michael Goodrich, Olga Ohrimenko and Roberto Tamassia
  Graph Drawing in the Cloud: Privately Visualizing Relational Data using Small Working Storage [+]

  We study graph drawing in a cloud-computing context where data is stored externally and processed using a small local working storage. We show that a number of classic graph drawing algorithms can be efficiently implemented in such a framework where the client can maintain privacy while constructing a drawing of her graph.

• Karsten Klein and Markus Chimani
  Shrinking the Search Space for Clustered Planarity [+]

  A clustered graph is a graph augmented with a hierarchical inclusion structure over its vertices, and arises very naturally in multiple application areas. While it is long known that planarity---i.e., drawability without edge crossings---of graphs can be tested in polynomial (linear) time, the complexity for the clustered case is still unknown. In this paper, we present a new graph theoretic reduction which allows us to considerably shrink the combinatorial search space, which is of benefit for all enumeration-type algorithms. Based thereon, we give new classes of polynomially testable graphs and a practically efficient exact planarity test for general clustered graphs based on an integer linear program.

• Mirza Klimenta and Ulrik Brandes
  Graph Drawing by Classical Multidimensional Scaling: New Perspectives [+]

  With shortest-path distances as input, classical multidimensional scaling can be regarded as a spectral graph drawing algorithm, and recent approximation techniques make it scale to very large graphs. In comparison with other methods, however, it is considered inflexible and prone to degenerate layouts for some classes of graphs. We want to challenge this belief by demonstrating that the method can be flexibly adapted to provide focus+context layouts. Moreover, we propose an alternative instantiation that appears to be more suitable for graph drawing and prevents certain degeneracies.

• Stephen G. Kobourov, Debajyoti Mondal and Rahnuma Islam Nishat
  Touching Triangle Representation for 3-Connected Planar Graphs [+]

  A touching triangle graph representation (TTG) of a planar graph is a planar drawing Γ of the graph, where each vertex is represented as a triangle and each edge e is represented as a side contact of the triangles that correspond to the endvertices of e. We call Γ a proper TTG if Γ determines a tiling of a triangle, where each tile corresponds to a distinct vertex of the input graph. In this paper we prove that every 3-connected cubic planar graph admits a proper TTG. We also construct proper TTG for parabolic grid graphs and the graphs determined by rectangular grid drawings (e.g., square grid graphs). Finally, we describe a fixed-parameter tractable decision algorithm for testing whether a 3-connected planar graph admits a proper TTG.

• Gabriel Nivasch, János Pach and Gábor Tardos
  The visible perimeter of an arrangement of disks [+]

  Given a collection of n opaque unit disks in the plane, we want to stack them on top of each other in an order so as to maximize the total length of all pieces of their boundaries visible from above. We call this total length the "visible perimeter" of the collection with respect to the particular order. We prove that if the centers of the disks form a dense point set, i.e., the ratio of the maximum distance to the minimum distance between them is O(n^1/2), then there is a stacking order for which the visible perimeter is Omega(n^2/3). We also show that the order of magnitude of this bound cannot be improved in the case of the n^1/2 by n^1/2 piece of a sufficiently small square grid. On the other hand, if the set of centers is dense and the maximum distance between them is small, then the visible perimeter is O(n^3/4) with respect to any stacking order. We construct collections of disks for which the order of magnitude of this bound is tight. The above results partially answer some questions raised by Cabello, Haverkort, van Kreveld, and Speckmann.

• Martin Nöllenburg, Roman Prutkin and Ignaz Rutter
  Edge-weighted contact representations of planar graphs [+]

  We study contact representations of edge-weighted planar graphs, where vertices are rectangles or rectilinear polygons and edges are polygon contacts whose lengths represents the edge weights. We show that for any given edge-weighted planar graph that is internally triangulated and has no separating triangles we can construct in linear time an edge-proportional rectangular dual if one exists and report failure otherwise. For a given combinatorial structure of the contact representation and edge weights interpreted as lower bounds on the contact lengths, a corresponding contact representation that minimizes the size of the enclosing rectangle can be found in linear time. If, on the other hand, the combinatorial structure is not fixed, we prove NP-hardness of deciding whether a contact representation with lower and upper bounded contact lengths exists. Finally, we give a complete characterization of the rectilinear polygon complexity required for representing biconnected internally triangulated graphs: For outerplanar graphs complexity 8 is sufficient and necessary, and for graphs with two adjacent or multiple non-adjacent internal vertices the complexity is unbounded.

• Zahed Rahmati, Sue Whitesides and Valerie King
  Kinetic and Stationary Point-Set Embeddability for Plane Graphs [+]

  We investigate a kinetic version of point-set embeddability. Given a plane graph $G(V,E)$ where $|V|=n$, and a set $P$ of $n$ moving points where the trajectory of each point is an algebraic function of constant maximum degree $s$, we maintain a point-set embedding of $G$ on $P$ with at most three bends per edge during the motion. This requires reassigning the mapping of vertices to points from time to time. Our kinetic algorithm uses linear size, $O(n\log n)$ preprocessing time, and processes $O(n^2\beta_{2s+2}(n)\log n)$ events, each in $O(\log^2 n)$ time. Here, $\beta_s(n)=\lambda_s(n)/ n$ is an extremely slow-growing function and $\lambda_s(n)$ is the maximum length of Davenport-Schinzel sequences of order $s$ on $n$ symbols. Also, we give an $O(n\log n)$ algorithm for the point-set embedding of the graph $G$ on stationary points $P$ with at most two bends per edge; this improves the previous $O(n^2)$ algorithm by Kaufmann and Wiese.

• Andres J. Ruiz-Vargas
  Tangles and Degenerate Tangles [+]

  We study some variants of Conway's thrackle conjecture. A tangle is a graph drawn in the plane such that its edges are represented by continuous arcs, and any two edges share precisely one point, which is either a common endpoint or an interior point at which the two edges are tangent to each other. These points of tangencies are assumed to be distinct. If we drop the last assumption, that is, more than two edges may touch one another at the same point, then the drawing is called a degenerate tangle. We settle a problem of Pach, Radoi\v ci\'c, and T\'oth, by showing that every degenerate tangle has at most as many edges as vertices. We also give a complete characterization of tangles.

• Marcus Schaefer
  Toward a Theory of Planarity: Hanani-Tutte and Planarity Variants [+]

  We study Hanani-Tutte style theorems for various notions of planarity, including partially embedded planarity, and simultaneous planarity. This approach brings together the combinatorial, computational and algebraic aspects of planarity notions and may serve as a uniform foundation for planarity, as suggested in the writings of Tutte and Wu.

• Micha Sharir and Adam Sheffer
  Counting Plane Graphs: Cross-Graph Charging Schemes [+]

  We study cross-graph charging schemes for graphs drawn in the plane. These are charging schemes where charge is moved across vertices of different graphs. Such methods have been recently applied to obtain various properties of triangulations that are embedded over a fixed set of points in the plane. We show how this method can be generalized to obtain results for various other types of graphs that are embedded in the plane. Specifically, we obtain a new bound of O(187.53^N) for the maximum number of crossing-free straight-edge graphs that can be embedded over any specific set of N points in the plane (improving upon the previous best upper bound 207.85^N in Hoffmann et al.). We also derive upper bounds for numbers of several other types of plane graphs (such as connected and bi-connected plane graphs), and obtain various bounds on expected vertex-degrees in graphs that are uniformly chosen from the set of all crossing-free straight-edge graphs that can be embedded over a specific point set. We then show how to apply the cross-graph charging-scheme method for graphs that allow certain types of crossings. Specifically, we consider graphs with no set of k pairwise-crossing edges (more commonly known as k-quasi-planar graphs). For k = 3 and k = 4, we prove that, for any set S of N points in the plane, the number of graphs that have a straight-edge k-quasi-planar embedding over S is only exponential in N.

• Andrew Suk
  Density theorems for intersection graphs of $t$-monotone curves [+]

  A curve $\gamma$ in the plane is $t$-monotone if its interior has at most $t-1$ vertical tangent points. A family of $t$-monotone curves $F$ is \emph{simple} if any two members intersect at most once. It is shown that if $F$ is a simple family of $n$ $t$-monotone curves with at least $\epsilon n^2$ intersecting pairs (disjoint pairs), then there exists two subfamilies $F_1,F_2 \subset F$ of size $\delta n$ each, such that every curve in $F_1$ intersects (is disjoint to) every curve in $F_2$, where $\delta$ depends only on $\epsilon$. We apply these results to find pairwise disjoint edges in simple topological graphs.

• Kevin Verbeek
  Homotopic C-oriented Routing [+]

  We study the problem of finding non-crossing minimum-link C-oriented paths that are homotopic to a set of input paths in an environment with C-oriented obstacles. We introduce a special type of C-oriented paths---smooth paths---and present a 2-approximation algorithm that runs in $O(n^2 (n + \log \kappa) + k_{in} \log n)$ time, where $n$ is the total number of paths and obstacle vertices, $k_{in}$ is the total number of links in the input, and $\kappa = |C|$. The algorithm also computes an $O(\kappa)$-approximation for general C-oriented paths. As a related result we show that, given a set of C-oriented paths with $L$ links in total, non-crossing C-oriented paths homotopic to the input paths can require a total of $\Omega(L \log \kappa)$ links.

Track 2: Visualization systems and interfaces

• Daniel Archambault and Helen Purchase
  Mental Map Preservation Helps User Orientation in Dynamic Graphs [+]

  We present the results of a formal experiment that tests the ability of a participant to orient themselves in a dynamically evolving graph. Examples of these tasks include finding a specific location or route between two locations. We find that preserving the mental map for the tasks tested is significantly faster and produces fewer errors. As the number of targets increase, this result holds. This formal experiment is the first to demonstrate a significant positive effect for preserving the mental map when presenting a dynamic graph.

• Christopher Auer, Christian Bachmaier, Franz Josef Brandenburg, Andreas Gleißner and Josef Reislhuber
  Optical Graph Recognition [+]

  Optical graph recognition (OGR) reverses graph drawing. A drawing transforms the topological structure of a graph into a graphical representation. Primarily, it maps vertices to points and displays them by icons and it maps edges to Jordan curves connecting the endpoints. OGR transforms the digital image of a drawn graph into its topological structure. It consists of four phases, preprocessing, segmentation, topology recognition, and postprocessing. OGR is based on established digital image processing techniques. Its novelty is the topology recognition where the edges are recognized with emphasis on the attachment to their vertices and on edge crossings. Our prototypical implementation OGRup shows the effectiveness of the approach and produces a GraphML file which can be used for further algorithmic studies and graph drawing tools.

• Benjamin Bach, Andre Spritzer, Evelyne Lutton and Jean-Daniel Fekete
  Interactive Random Graph Generation with Evolutionary Algorithms [+]

  Generating random graphs with particular characteristics is crucial for evaluating graph algorithms, layouts and visualization techniques. Current random graph generators provide limited control on the final characteristics of the graphs they generate. The situation is even harder when one wants to generate random graphs similar to a given graph since the measures that contribute to the similarity can be difficult to select, implying a long and painful iterative process from random generation with a specified set of parameters to visual inspection back and forth. This task can be automatized as an optimization process as the search of an optimal graph template fitting some complex conditions, as well as some subjective assessment (aesthetic, visual appreciation). This article introduces the system called GraphCuisine that monitors and controls a random graph generation process; it is based on an interactive Evolutionary Algorithm that performs a search in a space of graphs generation parameters. We describe the graph generation process from a user’s perspective, explain the underlying techniques and demonstrate how it can generate graphs that approach a target set of measures or mimic an existing graph by interactively refining the measures and their importance contributing to the similarity.

• Michael J. Bannister, David Eppstein, Michael T. Goodrich and Lowell Trott
  Force-Directed Graph Drawing Using Social Gravity and Scaling [+]

  Force-directed layout algorithms produce graph drawings by resolving a system of emulated physical forces. We present techniques for using social gravity as an additional force in force-directed layouts, together with a scaling technique, to produce drawings of trees and forests, as well as more complex social networks. Social gravity assigns mass to vertices in proportion to their net- work centrality, which allows vertices that are more graph-theoretically central to be visualized in physically central locations. Scaling varies the gravitational force throughout the simulation, and reduces crossings relative to unscaled gravity. In addition to providing this algorithmic framework, we apply our algorithms to social networks produced by Mark Lombardi, and we show how social gravity can be incorporated into force-directed Lombardi-style drawings.

• Sandra Bies and Marc Van Kreveld
  Time-Space Maps from Triangulations [+]

  Time-space maps show travel time as distances on a map. We discuss the case of time-space maps with a single center; here the travel times from a single source location to a number of destinations are shown by their distances. To accomplish this while maintaining recognizability, the input map must be deformed in a suitable manner. We present three different methods and analyze them experimentally.

• Martin Fink, Herman Haverkort, Martin Nöllenburg, Maxwell Roberts, Julian Schuhmann and Alexander Wolff
  Drawing Metro Maps using Bézier Curves [+]

  The automatic layout of metro maps has been investigated quite intensely over the last few years. Previous work has focused on the \emph{octilinear} drawing style where edges are drawn horizontally, vertically, or diagonally at $45^\circ$. Inspired by work on manually created curvy metro maps, we advocate the use of the \emph{curvilinear} drawing style; we draw edges as Bézier curves. Since we forbid metro lines to bend (even in stations), the user of such a map can trace the metro lines easily. In order to create such drawings, we use the force-directed framework. Our method is the first that directly represents and operates on edges as Bézier curves.

• J. Joseph Fowler and Stephen Kobourov
  Planar Preprocessing for Spring Embedders [+]

  Spring embedders are conceptually simple and produce "organic" straight-line drawings with an undeniable aesthetic appeal, which explains their prevalence when it comes to automated graph drawing. However, when drawing planar graphs, spring embedders often produce non-plane drawings, as edge crossings do not factor into the objective function being minimized. On the other hand, there are fairly straightforward algorithms for creating plane straight-line drawings for planar graphs, but the resulting layouts generally are not aesthetically pleasing, as vertices are often grouped in small regions and edges lengths can vary dramatically. It is known that the initial layout influences the output of a spring embedder, and yet a random layout is nearly always the default. We study the eect of using various plane initial drawings as an inputs to a spring embedder, measuring the percent improvement in reducing crossings and increasing node separation, edge length uniformity, and angular resolution.

• Emden Gansner, Yifan Hu and Stephen North
  Visualizing Streaming Text Data with Dynamic Graphs and Maps [+]

  The many endless rivers of text now available present a serious challenge in the task of gleaning, analyzing and discovering useful information. In this paper, we describe a methodology for visualizing text streams in real time. The approach automatically groups similar messages into ``countries,'' with keyword summaries, using semantic analysis, graph clustering and map generation techniques. It handles the need for visual stability across time by dynamic graph layout and Procrustes projection techniques, enhanced with a novel stable component packing algorithm. The result provides a continuous, succinct view of evolving topics of interest. To make these ideas concrete, we describe their application to an online service called TwitterScope, available at http://bit.ly/HA6KIR.

• Martin Gronemann and Michael Jünger
  Drawing Clustered Graphs as Topographic Maps [+]

  The visualization of clustered graphs is an essential tool for the analysis of networks, in particular, social networks, in which clustering techniques like community detection can reveal various structural properties. In this paper, we show how clustered graphs can be drawn as topographic maps, a type of map easily understandable by users not familiar with information visualization. Elevation levels of connected entities correspond to the nested structure of the cluster hierarchy. We present methods for initial node placement and describe a tree mapping based algorithm that produces an area efficient layout. Given this layout, a triangular irregular mesh is generated that is used to extract the elevation data for rendering the map. In addition, the mesh enables the routing of edges based on the topographic features of the map.

• Evgenios M. Kornaropoulos and Ioannis G. Tollis
  DAGView: An Approach for Visualizing Large Graphs [+]

  In this paper, we propose a novel visualization framework called DAGView which contains a family of algorithms based on the Overloaded Orthogonal technique~\cite{DBLP:conf/gd/KornaropoulosT11}. The aim of DAGView is to produce clear visualizations of directed acyclic graphs in which every edge and the potential existence of a path can be immediately spotted by the user. Several criteria that users identified as important in a layout are met, such as underlying grid, crossings that appear perpendicular, easy check for the existence of an edge and/or path. The main algorithm is based on the layout of directed acyclic graphs but can be extended to handle directed graphs with cycles and undirected graphs, taking into account user preferences and/or constraints. Finally we discuss important features of our approach that respect the user's choices as described in~\cite{Ghoniem:2004:CRG:1038262.1038777,5674033,DBLP:conf/gd/Purchase97}.

• Quan Nguyen, Peter Eades and Seok-Hee Hong
  StreamEB: Stream Edge Bundling [+]

  {\em Graph streams} have been extensively studied, for instance, for data mining and for stream reasoning, while a fairly limited number of studies have been conducted on visualizations. Recently, {\em edge bundling} methods has been extensively investigated to reduce visual clutter in large graph visualizations, however, have focused on {\em static} graphs. This paper present a new framework, namely \modelname, for edge bundling of graph streams, which integrates temporal, neighborhood, data-driven and spatial compatibility for edges. Amongst these metrics, {\em temporal compatibility} and {\em neighborhood compatibility} are introduced for the first time, whereas the other metrics have not yet been studied for graph streams. Based on the framework, we present two bundling methods, called FStreamEB (Force-directed Stream Edge Bundling) and TStreamEB (Tree-based Stream Edge Bundling). We demonstrate effectiveness of our framework using US flights data and Thompson-Reuters stock data.

• Helen Purchase, John Hamer, Martin Nöllenburg and Stephen Kobourov
  On The Usability of Lombardi Graph Drawings [+]

  A recent line of work in graph drawing studies Lombardi drawings, i.e., drawings with circular-arc edges and perfect angular resolution at vertices. Little has been known about the effects of curved edges versus straight edges in typical graph reading tasks. In this paper we present the first user evaluation that empirically measures the readability of three different layout algorithms (traditional spring embedder and two recent near-Lombardi force-based algorithms) for three different tasks (shortest path, common neighbor, vertex degree). The results indicate that, while users prefer the Lombardi drawings, the performance data do not present such a positive picture.

• Arnaud Sallaberry, Chris Muelder and Kwan-Liu Ma
  Clustering, visualizing, and navigating for large dynamic graphs [+]

  While many works on network visualization have been devoted to static graphs, a few of them involve dynamic ones. In this paper, we present a new approach to exploring dynamic graphs. We first propose a new clustering algorithm for dynamic graphs which finds an ideal clustering for each timestep and links the clusters together. The resulting time-varying clusters are then used to define two visual representations. The first view is an overview that shows how clusters evolve over time and provides an interface to find and select interesting time-steps. The second view consists of a node link diagram of a selected time-step which uses the clustering to efficiently define the layout. By using the time-dependant clustering, we ensure the stability of our visualization and preserve user mental map by minimizing node motion, while simultaneously producing an ideal layout for each time step. Also, as the clustering is computed ahead of time, the second view updates in linear time which allows for interactivity even for graphs with upwards of tens of thousands of nodes.

• Till Tantau
  Graph Drawing in TikZ [+]

  At the heart of every good graph drawing algorithm lies an efficient procedure for assigning canvas positions to a graph's nodes and the bend points of its edges. However, every real-world implementation of such an algorithm must address numerous problems that have little to do with the actual algorithm, like handling input and output formats, formatting node texts, and styling nodes and edges. We present a new framework, implemented in the Lua programming language and integrated into the TikZ graphics description language, that aims at simplifying the implementation of graph drawing algorithms. Implementers using the framework can focus on the core algorithmic ideas and will automatically profit from the framework's pre- and postprocessing steps as well as from the extensive capabilities of the TikZ graphics language. Algorithms already implemented using the framework include the Reingold-Tilford tree drawing algorithm, a modular version of Sugiyama's layered algorithm, and several force-based multilevel algorithms.