Md. Jawaherul Alam and Stephen G. Kobourov
Proportional Contact Representations of 4connected Planar Graphs [+]
In a contact representation of a planar graph, vertices are represented by interiordisjoint polygons and two polygons share a nonempty 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 4connected 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 10year old conjecture on the existence of a Hamiltonian canonical cycle in a 4connected 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 4connected planar graph admits a contact representation using only rectangles.
Soroush Alamdari and Therese Biedl
Open RectangleofInfluence Drawings of NonTriangulated Planar Graphs [+]
A straight line drawing of a graph is an open weak rectangle
ofinfluence (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 rectangleofinfluence
drawings, no algorithm is known to test whether a graph has a planar
open weak RIdrawing.
In a recent paper, we showed how to test, for innertriangulated planar
graphs, whether they have a planar open weak RIdrawing 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 RIdrawing is
NPcomplete. NPcompleteness holds even for open weak RIdrawings
with nonaligned frames.
Soroush Alamdari, Timothy M. Chan, Elyot Grant, Anna Lubiw and Vinayak Pathak
SelfApproaching Graphs [+]
In this paper we introduce selfapproaching graph drawings. A straightline drawing of a graph is selfapproaching 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.33spanner. We study three topics: (1) recognizing selfapproaching drawings; (2) constructing selfapproaching drawings of a given graph; (3) constructing a selfapproaching Steiner network connecting a given set of points. We show that: (1) there are efficient algorithms to test if a polygonal path is selfapproaching in R^2 and R^3, but it is NPhard to test if a given graph drawing in R^3 has a selfapproaching $uv$path; (2) we can characterize the trees that have selfapproaching drawings; (3) for any given set of terminal points in the plane, we can find a linear sized network that has a selfapproaching 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 preassigned to page $1$, and the edges of $E_2$ are preassigned 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{hntpbesg09tr} give an interesting and complex linear time algorithm for tackling \belong
based on SPQRtrees.
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
CircleRepresentations of Simple 4Regular Planar Graphs [+]
Lov\'asz conjectured that every connected 4regular 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 3connected, and, (b)~we
demonstrate an infinite class of connected 4regular planar graphs
which are not 3connected 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 axisaligned line segments, in smooth
orthogonal layouts every edge is made of axisaligned 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 4planar graph
has a smooth orthogonal layout with edge complexity 3. If the input
graph has a complexity2 traditional orthogonal layout we can
transform it into a smooth complexity2 layout. Using the Kandinsky
model for removing the degree restriction, we show that any planar
graph has a smooth complexity2 layout.
Gregor Betz, Christof Doll, Andreas Gemsa, Ignaz Rutter and Dorothea Wagner
Columnbased Graph Layouts [+]
We consider orthogonal upward drawings of directed acyclic graphs (DAGs) with nodes of uniform width but nodespecific 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 layerfree upward crossing minimization algorithm suggested by Chimani et al. and integrate it into the topologyshapemetric (TSM) framework introduced by Tamassia. This in combination with an algorithm by Biedl and Kant lets us generate columnbased layouts, i.e., layouts where the plane is divided into uniformwidth columns and every node is assigned to a column.
We show that our columnbased 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 realworld 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{CCtree} representing all embeddings of~$G$ that extend to planar embeddings of~$\1G$. We show that CCtrees can be computed in linear time, and that their intersection is again a CCtree. This yields a lineartime algorithm for {\sc SEFE} if all input graphs share the same set of disjoint cycles. These results, including the CCtree, 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 1Planar Graphs [+]
A graph is 1planar if it can be drawn in the plane such that each edge is crossed at most once. It is maximal 1planar if the addition of any edge violates 1planarity.
Maximal 1planar graphs have at most 4 n  8 edges. We show that there are sparse maximal 1planar graphs with only 45/17 n + O(1) edges. With a fixed rotation system there are maximal 1planar graphs with only 7/3 n + O(1) edges, which is sparser than maximal planar graphs. There cannot be maximal 1planar 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 1planar rotation system of a graph uniquely determines its 1planar 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. interiordisjoint axisaligned 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 nonzero 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 axisaligned 3D boxes. We prove that
it is NPcomplete 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 straightline drawings
of nonplanar 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 stubedge 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 straightline drawing contains. We
present an efficient solution for 2planar drawings and a
2approximation algorithm for the dual problem.
Luca Castelli Aleardi, Olivier Devillers and Eric Fusy
Canonical ordering for triangulations on the cylinder, with applications to periodic straightline drawings [+]
We extend the notion of canonical orderings to cylindric triangulations. This allows us to extend the incremental straightline drawing algorithm of
de Fraysseix et al. to this setting. Our algorithm yields in linear time
a crossingfree straightline 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 byproduct, we can also obtain in linear time a crossingfree straightline 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 noncontractible cycle. Since $c\leq\sqrt{2n}$, the grid area is $O(n^{5/2})$.
Steven Chaplick and Torsten Ueckerdt
Planar Graphs as VPGGraphs [+]
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 4connected 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 trianglefree planar graphs are contact graphs of: Lshapes, \Gshapes, 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 2DIR.
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 NPcomplete 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 branchandbound 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 selfcrossing) covering path consisting of
$n/2 +O(n/\log{n})$ straight line segments.
If no three points are collinear, any covering path (selfcrossing or
noncrossing) needs at least $n/2$ segments.
If the path is required to be noncrossing, $n1$ 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 noncrossing
covering path for $n$ points in the plane requires $\Omega(n \log{n})$
time in the worst case.
Peter Eades, SeokHee Hong, Naoki Katoh, Giuseppe Liotta, Pascal Schweitzer and Yusuke Suzuki
Testing Maximal 1planarity of Graphs with a Rotation System in Linear Time [+]
A {\em 1planar} graph is a graph that can be embedded in the plane with at most one crossing per edge. A 1planar graph on~$n$ vertices can have at most $4n8$ edges. It is known that testing 1planarity of a graph is NPcomplete. A 1planar embedding of a graph $G$ is {\em maximal}, if no edge can be added without violating the 1planarity of $G$. In this paper, we study combinatorial properties of maximal 1planar embeddings. In particular, we show that in a maximal 1planar embedding, the graph induced by the noncrossing edges is spanning and biconnected. Using the properties, we show that the problem of testing maximal 1planarity 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 1planar 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 1plane 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 threedimensional hyperbolic geometry. We also use circle packing to construct planar Lombardi drawings of a special class of 4regular planar graphs, the medial graphs of polyhedral graphs, and we show that not every 4regular planar graph has a Lombardi drawing. We have implemented our algorithm for 3connected planar cubic graphs.
Fabrizio Frati, Marc Glisse, William Lenhart, Giuseppe Liotta, Tamara Mchedlidze and Rahnuma Islam Nishat
PointSet Embeddability of 2Colored Trees [+]
In this paper we study bichromatic pointset embeddings of
$2$colored trees on $2$colored point sets, i.e., pointset
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
pointset embedding on a given convex point set is an $\cal
NP$complete problem; we also show that the same problem is
lineartime solvable if the convex point set does not contain two
consecutive points with the same color. Furthermore, we prove a $3n/2O(1)$
lower bound and a $2n$ upper bound (a $7n/6O(\log n)$ lower bound
and a $4n/3$ upper bound) on the minimum size of a universal point
set for straightline 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
pointset 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 cloudcomputing 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 planarityi.e., drawability without edge crossingsof 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 enumerationtype 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 shortestpath 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 inﬂexible and prone to degenerate layouts for some classes of graphs.
We want to challenge this belief by demonstrating that the method can be ﬂexibly 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 3Connected 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 3connected 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 ﬁxedparameter tractable decision algorithm for testing whether a 3connected 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
Edgeweighted contact representations of planar graphs [+]
We study contact representations of edgeweighted 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 edgeweighted planar graph that is internally triangulated and has no separating triangles we can construct in linear time an edgeproportional 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 NPhardness 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 nonadjacent internal vertices the complexity is unbounded.
Zahed Rahmati, Sue Whitesides and Valerie King
Kinetic and Stationary PointSet Embeddability for Plane Graphs [+]
We investigate a kinetic version of pointset 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 pointset 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 slowgrowing function and $\lambda_s(n)$ is the maximum length of DavenportSchinzel sequences of order $s$ on $n$ symbols. Also, we give an $O(n\log n)$ algorithm for the pointset 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. RuizVargas
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: HananiTutte and Planarity Variants [+]
We study HananiTutte 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: CrossGraph Charging Schemes [+]
We study crossgraph 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 crossingfree straightedge 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 biconnected plane graphs), and obtain various bounds on expected vertexdegrees in graphs that are uniformly chosen from the set of all crossingfree straightedge graphs that can be embedded over a specific point set.
We then show how to apply the crossgraph chargingscheme method
for graphs that allow certain types of crossings. Specifically, we consider
graphs with no set of k pairwisecrossing edges (more commonly known
as kquasiplanar 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
straightedge kquasiplanar 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 $t1$ 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 Coriented Routing [+]
We study the problem of finding noncrossing minimumlink Coriented paths that are homotopic to a set of input paths in an environment with Coriented obstacles. We introduce a special type of Coriented pathssmooth pathsand present a 2approximation 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 Coriented paths. As a related result we show that, given a set of Coriented paths with $L$ links in total, noncrossing Coriented paths homotopic to the input paths can require a total of $\Omega(L \log \kappa)$ links.
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 JeanDaniel 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
ForceDirected Graph Drawing Using Social Gravity and Scaling [+]
Forcedirected 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 forcedirected 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 graphtheoretically 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 forcedirected Lombardistyle drawings.
Sandra Bies and Marc Van Kreveld
TimeSpace Maps from Triangulations [+]
Timespace maps show travel time as distances on a map.
We discuss the case of timespace 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 forcedirected 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" straightline 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 nonplane 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 straightline 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 SeokHee 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, datadriven 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 (Forcedirected Stream Edge Bundling) and TStreamEB (Treebased Stream Edge Bundling).
We demonstrate effectiveness of our framework using US flights data and ThompsonReuters 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 circulararc 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 nearLombardi
forcebased 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 KwanLiu 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 timevarying 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 timesteps. The second view consists of a node link diagram of a selected timestep which uses the clustering to efficiently define the layout. By using the timedependant 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 realworld 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 ReingoldTilford tree drawing algorithm, a modular version of Sugiyama's layered algorithm, and several forcebased multilevel algorithms.
