Accepted papers

Abstract: If a graph embeds in a surface with k crosscaps, does it always have an embedding in the same surface in which every edge passes through each crosscap at most once? This well-known open problem can be restated using crossing numbers: the degenerate crossing number, dcr(G), of G equals the smallest number k so that G has an embedding in a surface with k crosscaps in which every edge passes through each crosscap at most once. The genus crossing number, gcr(G), of G equals the smallest number k so that G has an embedding in a surface with k crosscaps. The question then becomes whether dcr(G) = gcr(G), and it is in this form that it was first asked Mohar.
We show that dcr(G) <= 6 gcr(G), and dcr(G) = gcr(G) as long as dcr(G) <= 3. We can separate dcr and gcr for (single-vertex) graphs with embedding schemes, but it is not clear whether the separating example can be extended into separations on simple graphs. Finally, we show that if a graph can be embedded in a surface with crosscaps, then it has an embedding in that surface in which every edge passes through each
crosscap at most twice.

Abstract: It is well-known that every graph with maximum degree 4 has an orthogonal drawing with area at most $\frac{49}{64}n^2+O(n)\approx 0.76n^2$. In this paper, we show that if the graph is 3-connected, then the area can be reduced even further to $\frac{25}{36}n^2+O(n) \approx 0.56n^2$. The drawing uses the 3-canonical order for (not necessarily planar) 3-connected graphs, which can be computed in linear time from the Mondshein-sequence. To our knowledge, this is the first application of the 3-canonical order on non-planar graphs in graph-drawing.

Abstract: We consider two variants of the fundamental question of determining whether a simply connected flexible combinatorial structure can be realized in Euclidean space. Two models are considered: body-and-joint frameworks and contact graphs of unit disks in the plane. (1) We show that it is strongly NP-hard to decide whether a given polygonal linkage (body-and-bar framework) is realizable in the plane when the bodies are convex polygons and their contact graph is a tree; the problem is weakly NP-hard already for a chain of rectangles; but efficiently decidable for a chain of triangles hinged at distinct vertices. (2) We also show that it is strongly NP-hard to decide whether a given tree is the contact graph of interior-disjoint unit disks in the plane.

Abstract: The approach by Sugiyama et al. is widely used to automatically draw directed graphs. One of its step is to assign horizontal coordinates to nodes. Brandes and Köpf presented a method that proved to work well in practice. We extend this method to make it possible to draw diagrams with nodes that have considerably different sizes and edges that have fixed attachment points on a node's perimeter (ports). Our extensions integrate seamlessly with the original method and preserve the linear execution time.

Abstract: For every integer n ≥ 4, we construct a planar point set S_n of size 6n-10 such that every n-vertex planar graph G admits a plane embedding in which the vertices are mapped to points in S_n, and every edge is either a line segment or a polyline with one bend, where the bend point is also in S_n.

Abstract: Disk contact representations realize graphs by mapping vertices bijectively to interior-disjoint disks in the plane such that two disks touch each other if and only if the corresponding vertices are adjacent in the graph. Deciding whether a vertex-weighted planar graph can be realized such that the disks' radii coincide with the vertex weights is known to be NP-hard. In this work, we reduce the gap between hardness and tractability by analyzing the problem for special graph classes. We show that it remains NP-hard for outerplanar graphs with unit weights and for stars with arbitrary weights, strengthening the previous hardness results. On the positive side, we present constructive linear-time recognition algorithms for caterpillars with unit weights and for embedded stars with arbitrary weights.

Abstract: The visual analysis of complex networks is a challenging task in many fields, such as systems biology or social sciences. Often, various domain experts work together to improve the analysis time or the quality of the analysis results. Collaborative visualization tools can facilitate the analysis process in such situations. We propose a new web-based visualization environment which supports distributed, synchronous and asynchronous collaboration. In addition to standard collaboration features like event tracking or synchronizing, our client/server-based system provides a rich set of visualization and interaction techniques for better navigation and overview of the input network. Changes made by specific analysts or even just visited network elements are highlighted on demand by heat maps. They enable us to visualize user behavior data without affecting the original graph visualization. We evaluate the usability of the heat map approach against two alternatives in a user experiment.

Abstract: Let R be a set of n red points and B be a set of n blue points in the Euclidean plane.
We study the problem of computing a planar drawing of a cycle of minimum length that contains vertices at points R ∪ B and alternates colors.
When these points are collinear, we describe a Θ(n log n)-time algorithm to find such a shortest alternating cycle where every edge has at most two bends. We extend our approach to compute shortest alternating paths in O(n²) time with two bends per edge and to compute shortest alternating cycles on 3-colored point-sets in O(n²) time with O(n) bends per edge. We also prove that for arbitrary k-colored point-sets, the problem of computing an alternating shortest cycle is NP-hard, where k is any positive integer constant.

Abstract: A drawing of a graph can be understood as an arrangement of geometric objects.
In the most natural setting the arrangement is formed by straight-line segments.
Every cubic planar 3-connected graph with n vertices has such a drawing with only n/2+3 segments, matching the lower bound.
This result is due to Mondal et al. [J. of Comb. Opt., 25], who gave an algorithm for constructing such drawings.

We introduce two new algorithms that also produce drawings with n/2+3 segments.
One algorithm is based on a sequence of dual edge contractions, the other
is based on a sequence of removed cycles. We also show a flaw in the algorithm
of Mondal et al. and present a fix for it. We then compare the performance of these three
algorithms by measuring angular resolution, edge length and face aspect ratio of the constructed drawings.
We observe that the corrected algorithm of Mondal et al. mostly outperforms the other algorithms, especially in terms of angular resolution.
However, the new algorithms perform better in terms of edge length and minimal face aspect ratio.

Abstract: Answering an open question from 2007, we construct infinite k-crossing-critical families of graphs which contain arbitrarily often vertices of any prescribed odd degree, for sufficiently large k. From this we derive that, for any set of integers D such that min(D)=3 and 3,4 ? D, and for all sufficiently large k there exists an infinite k-crossing-critical family such that the numbers in D are precisely the vertex degrees which occur arbitrarily often in this family. We also investigate what are the possible average degrees of such crossing-critical families.

Abstract: Let d and t be fixed positive integers, and let K^d_t,...,t denote the complete d-partite hypergraph with t vertices in each of its parts, whose hyperedges are the d-tuples of the vertex set with precisely one element from each part. According to a fundamental theorem of extremal hypergraph theory, due to Erdős, the number of hyperedges of a d-uniform hypergraph on n vertices that does not contain K^d_t,...,t as a subhypergraph, is n^d-1/td-1. This bound is not far from being optimal.

We address the same problem restricted to intersection hypergraphs of (d-1)-dimensional simplices in R^d. Given an n-element set S of such simplices, let H^d(S) denote the d-uniform hypergraph whose vertices are the elements of S, and a d-tuple is a hyperedge if and only if the corresponding simplices have a point in common. We prove that if H^d(S) does not contain K^d_t,...,t as a subhypergraph, then its number of edges is O(n) if d=2, and O(n^d-1+ε for any ε> 0 if d ≥3. This is almost a factor of n better than Erdős's above bound. Our result is tight, apart from the error term ε in the exponent.

In particular, for d=2, we obtain a theorem of Fox and Pach, which states that every K_t,t-free intersection graph of n segments in the plane has O(n) edges. The original proof was based on a separator theorem that does not generalize to higher dimensions. The new proof works in any dimension and is simpler: it uses size-sensitive cuttings, a variant of random sampling. We demonstrate the flexibility of this technique by extending the proof of the planar version of the theorem to intersection graphs of x-monotone curves.

Abstract: IC-planar graphs are those graphs that admit a drawing where no two crossed edges share an end-vertex and each edge is crossed at most once. They are a proper subfamily of the 1-planar graphs. Given an IC-planar graph G with n vertices, we present an O(n)-time algorithm that computes a straight-line drawing of G in quadratic area, and an O(n³)-time algorithm that computes a straight-line drawing of G with right-angle crossings in exponential area. Both these area requirements are worst-case optimal. We also show that it is NP-complete to test IC-planarity both in the general case and in the case in which a rotation system is fixed for the input graph. Furthermore, we describe a polynomial-time algorithm to test whether a set of matching edges can be added to a triangulated planar graph such that the resulting graph is IC-planar.

Abstract: Homophily is a concept in social network analysis that states that in a network a link is more probable, if the two individuals have a common characteristic. We study the question if an observer can assess homophily by looking at the node-link diagram of the network. We design an experiment that investigates three different layout algorithms and asks the users to estimate the degree of homophily in the displayed network. One of the layout algorithms is a classical force-directed method, the other two are designed to improve node distinction based on the common characteristic. We study how each of the three layout algorithms helps to get a fair estimate, and whether there is a tendency to over or underestimate the degree of homophily. The stimuli in our experiments use different network sizes and different proportions of the cluster sizes.

Abstract: Let G be a plane triangulated graph. A rectangular dual of G is a partition of a rectangle into a set of interior-disjoint rectangles, one for each vertex, such that two regions are adjacent if and only if the corresponding vertices are connected by an edge. A rectangular dual is sliceable if it can be recursively subdivided along horizontal or vertical lines. A graph is rectangular if it has a rectangular dual and sliceable if it has a sliceable rectangular dual. There is a clear characterization of rectangular graphs. However, a full characterization of sliceable graphs is still lacking. The currently best result (Yeap and Sarrafzadeh, 1995) proves that all rectangular graphs without a separating 4-cycle are sliceable. In this paper we introduce a recursively defined class of graphs, so-called rotating pyramids, which contain exactly one separating 4-cycle in their ``core''. We conjecture that configurations of rotating pyramids determine if a graph is sliceable. We verify this conjecture for the class of rectangular graphs that contain exactly one separating 4-cycle. The nonsliceable graphs in this class are exactly the graphs that reduce to rotating windmills: rotating pyramids with a specific corner assignment.

Abstract: We consider relations between the size, treewidth, and local crossing number (maximum crossings per edge) of graphs embedded on topological surfaces. We show that an n-vertex graph embedded on a surface of genus g with at most k crossings per edge has treewidth O((gkn)^1/2) and layered treewidth O(gk), and that these bounds are tight up to a constant factor. As a special case, the k-planar graphs with n vertices have treewidth O((kn)) and layered treewidth O(k), which are tight bounds that improve a previously known O(k^3/4n^1/2) treewidth bound. Additionally, we show that for g<m, every m-edge graph can be embedded on a surface of genus g with O((m/g)log²g) crossings per edge, which is tight to within a polylogarithmic factor.

Abstract: The straight skeleton of a polygon is the geometric graph obtained by tracing the vertices during a mitered offsetting process. It is known that the straight skeleton of a simple polygon is a tree, and one can naturally derive directions on the edges of the tree from the propagation of the shrinking process. In this paper, we ask the reverse question: Given a tree with directed edges, can it be the straight skeleton of a polygon? And if so, can we find a suitable simple polygon? We answer these questions for all directed trees where the order of edges around each node is fixed.

Abstract: Algorithms for laying out large graphs have seen significant progress in the past decade. However, browsing large graphs remains a challenge. Rendering thousands of graphical elements at once often results in a cluttered image, and navigating these elements naively can cause disorientation. To address this challenge we propose a method called GraphMaps, mimicking the browsing experience of online geographic maps.
GraphMaps creates a sequence of layers, where each layer refines the previous one. During graph browsing, GraphMaps chooses the layer corresponding to the zoom level, and renders only those entities of the layer that intersect the current viewport. The result is that, regardless of the graph size, the number of entities rendered at each view does not exceed a predefined threshold, yet all graph elements can be explored by the standard zoom and pan operations.
GraphMaps preprocesses a graph in such a way that during browsing, the geometry of the entities is stable, and the viewer is responsive. Our case studies indicate that GraphMaps is useful in gaining an overview of a large graph, and also in exploring a graph on a finer level of detail.

Abstract: Drawing large graphs appropriately is an important step for the visual analysis of data from real-world networks. Here we present a novel multilevel algorithm to compute a graph layout with respect to a recently proposed metric that combines layout stress and entropy. As opposed to previous work, we do not solve the linear systems of the maxent-stress metric with a typical numerical solver. Instead we use a simple local iterative scheme within a multilevel approach. To accelerate local optimization, we approximate long-range forces and use shared-memory parallelism. Our experiments validate the high potential of our approach, which is particularly appealing for dynamic graphs. In comparison to the previously best maxent-stress optimizer, which is sequential, our parallel implementation is on average 30 times faster already for static graphs (and still faster if executed on one thread) while producing a comparable solution quality.

Abstract: We propose a new family of quality metrics for graph drawing; in particular, we concentrate on larger graphs. We illustrate these metrics with examples and apply the metrics to data from previous experiments, leading to the suggestion that the new metrics are effective.

Abstract: In a fan-planar drawing of a graph there is no edge that crosses two other independent edges. We study 2-layer fan-planar drawings, i.e., fan-planar drawings such that the vertices are assigned to two distinct horizontal layers and edges are straight-line segments that connect vertices of different layers. We fully characterize 2-layer fan-planar drawable graphs and describe a linear-time testing and embedding algorithm for biconnected graphs. We also study the relationship between 2-layer fan-planar graphs and 2-layer right-angle crossing graphs.

Abstract: We present Kojaph, a new system for the visual definition and exploration of patterns in graph databases. It offers a powerful visual language integrated in a simple user interface, to define complex patterns as a combination of topological properties and node/edge attribute properties. Users can also interact with the query results and visually explore the graph incrementally, starting from such results. From the application perspective, Kojaph has been designed to run on top of every desired graph database management system (GDBMS). As a proof of concept, we integrated it with Neo4J, the most popular GDBMS.

Abstract: A graph has strong convex dimension 2, if it admits a straight-line drawing in the plane such that its vertices are in convex position and the midpoints of its edges are in convex position. Halman, Onn, and Rothblum conjectured that graphs of strong convex dimension 2 are planar and therefore have at most 3n-6 edges. We prove that all such graphs have at most 2n-3 edges while on the other hand we present a class of non-planar graphs of strong convex dimension 2. We also give lower bounds on the maximum number of edges a graph of strong convex dimension 2 can have and discuss variants of this graph class. We apply our results to questions about large convexly independent sets in Minkowski sums of planar point sets, that have been of interest in recent years.

Abstract: Motivated by visualization of large graphs, we introduce a new type of graph drawing called ``rook-drawing". A rook-drawing of a graph G is obtained by placing the n nodes of G on the intersections of a regular grid, such that each line and column of the grid supports exactly one node. This paper focuses on rook-drawings of planar graphs. We first give a linear algorithm to compute a planar straight-line rook-drawing for outerplanar graphs. We then show that there exist planar graphs which have no planar straight-line rook-drawing. Finally, we give a linear time algorithm to compute a polyline planar rook-drawing for plane graphs with at most n-3 bent edges.

Abstract: A simultaneous embedding with fixed edges (SEFE) of two planar graphs R and B is a pair of plane drawings of R and B that coincide when restricted to R\cap B. We show that whenever R and B admit a SEFE, they also admit a SEFE in which every edge is a polygonal curve with few bends and every pair of edges has few crossings. Specifically: (1) if R and B are trees then one bend per edge and four crossings per edge pair suffice (and one bend per edge is sometimes necessary), (2) if R is a planar graph and B is a tree then six bends per edge and eight crossings per edge pair suffice, and (3) if R and B are planar graphs then six bends per edge and sixteen crossings per edge pair suffice. Our results improve on a paper by Grilli et al. (GD'14), which proves that nine bends per edge suffice, and on a paper by Chan et al. (GD'14), which proves that twenty-four crossings per edge pair suffice.

Abstract: In a storyline visualization, we visualize a collection of interacting characters (e.g., in a movie, play, etc.) by x-monotone curves that converge for each interaction, and diverge otherwise. Given a storyline with n character interactions, we show tight lower and upper bounds on the number of crossings required in any storyline visualization for a restricted case. In particular, we show that if (1) each meeting consists of exactly two characters and (2) the meetings can be modeled as a tree, then we can always find a storyline visualization with O(n log n) crossings. Furthermore, we show that there exist storylines in this restricted case that require Ω(n log n) crossings. Lastly, we show that, in the general case, computing a storyline visualization with a minimum number of crossings is fixed-parameter tractable, when parameterized on the number of characters k. Our algorithm runs in time O(k!^2k log k + k!^2n)$, where n is the number of meetings.

Abstract: A point set S ⊂ R² is universal for a class G if every graph of G has a planar straight-line embedding on S. It is well-known that the integer grid is a quadratic-size universal point set for planar graphs, while the existence of a sub-quadratic universal point set for them is one of the most fascinating open problems in Graph Drawing. Motivated by the fact that outerplanarity is a key property for the existence of small universal point sets, we study 2-outerplanar graphs and provide for them a universal point set of size O(n log n).

Abstract: In this paper we show how techniques developed for untangling planar graphs by Bose et. al. [Discrete & Computational Geometry 42(4): 570-585 (2009)] and Goaoc et. al [Discrete & Computational Geometry 42(4): 542-569 (2009)] imply new results about some recent graph drawing models. These include column planarity, universal point subsets, and partial simultaneous geometric embeddings (with or without mappings). Some of these results answer open problems posed in previous papers.

Abstract: An obstacle representation of a graph G is a set of points in the plane representing the vertices of G, together with a set of polygonal obstacles such that two vertices of G are connected by an edge in G if and only if the line segment between the corresponding points avoids all the obstacles. The obstacle number obs(G) of G is the minimum number of obstacles in an obstacle representation of G.

We provide the first non-trivial general upper bound on the obstacle number of graphs by showing that every n-vertex graph satisfies obs(G) <= 2n log(n). This refutes a conjecture of Mukkamala, Pach, and Pálvölgyi. For bipartite n-vertex graphs, we improve this bound to n-1. Both bounds apply even when the obstacles are required to be convex.

We also prove a lower bound 2^Ω(hn) on the number of n-vertex graphs with obstacle number at most h for h < n and an asymptotically matching lower bound Ω(n^4/3M^2/3) for the complexity of a collection of M ≥ Ω(n) faces in an arrangement of n² line segments with 2n endpoints.

Abstract: We study contact representations for graphs, which we call pixel representations in 2D and voxel representations in 3D. Our representations are based on the unit square grid whose cells we call pixels in 2D and voxels in 3D. Two pixels are adjacent if they share an edge, two voxels if they share a face. We call a connected set of pixels or voxels a blob. Given a graph, we represent its vertices by disjoint blobs such that two blobs contain adjacent pixels or voxels if and only if the corresponding vertices are adjacent. We are interested in the size of a representation, which is the number of pixels or voxels it consists of.
We first show that finding minimum-size representations is NP-complete. Then, we bound representation sizes needed for certain graph classes. In 2D, we show that, for k-outerplanar graphs with n vertices, Θ(kn)$ pixels are always sufficient and sometimes necessary. In particular, outerplanar graphs can be represented with a linear number of pixels, whereas general planar graphs sometimes need a quadratic number. In 3D, Θ(n²) voxels are always sufficient and sometimes necessary for any n-vertex graph. We improve this bound to Θ(n τ) for graphs of treewidth τ and to O((g+1)² n log²n) for graphs of genus g. In particular, planar graphs admit representations with O(n log²n) voxels.

Abstract: Set membership of points in the plane can be visualized by connecting corresponding points via graphical features, like paths, trees, polygons, ellipses. In this paper we study the bus embeddability problem (BEP): given a set of colored points we ask whether there exists a planar realization with one horizontal straight-line segment per color, called bus, such that all points with the same color are connected with vertical line segments to their bus. We present an ILP and an FPT-approach for the general problem. For restricted versions of this problem, such as when the relative order of buses is predefined, or when a bus must be placed above all its points, we provide efficient algorithms. We show that another restricted version of the problem can be solved using 2-stack pushall sorting. On the negative side we prove the NP-completeness of a special case of BEP.

Abstract: Boundary labeling deals with annotating features in images such that labels are placed outside of the image and are connected by curves (so-called leaders) to the corresponding features. While boundary labeling has been extensively investigated from an algorithmic perspective, the research on its readability has been neglected. In this paper we present the first formal user study on the readability of boundary labeling. We consider the four most studied leader types with respect to their performance, i.e., whether and how fast a viewer can assign a feature to its label and vice versa. We give a detailed analysis of the results regarding the readability of the four models and discuss their aesthetic qualities based on the users’ preference judgments and interviews.

Abstract: Motivated by a paper of Babilon et al. entitled ``Visibility Representations of Complete Graphs'' we study the following problem. Let C={C_1,..., C_n} denote a collection of translates of a regular convex k-gon in the plane with the stacking order. The collection C forms a visibility clique if for every i<j the intersection of C_i and C_j is not covered by the elements that are stacked between them, i.e., (C_i∩ C_j) ∖ ∪_i<k<j C_k ≠ ∅.
We show that if C forms a visibility clique its size is bounded from above by O(k⁴) thereby improving the upper bound of 2^2k from the aforementioned paper. We also obtain an upper bound of 2^{2(k choose 2)+2} on the size of a visibility clique for homothetes of a convex (not necessarily regular) k-gons.

Abstract: An abstract topological graph (briefly an AT-graph) is a pair A=(G,X) where G=(V,E) is a graph and X⊂ (E choose 2) is a set of pairs of its edges. The AT-graph A is simply realizable if G can be drawn in the plane so that each pair of edges from X crosses exactly once and no other pair crosses. We characterize simply realizable complete AT-graphs by a finite set of forbidden AT-subgraphs, each with at most six vertices. This implies a straightforward polynomial algorithm for testing simple realizability of complete AT-graphs, which simplifies a previous algorithm by the author.

Abstract: We provide a pipeline for generating syntax diagrams (also called railroad diagrams) from context free grammars. Syntax diagrams are a graphical representation of a context free language, which we formalize abstractly as a set of mutually recursive nondeterministic finite automata and draw by combining elements from the confluent drawing, layered drawing, and smooth orthogonal drawing styles. Within our pipeline we introduce several heuristics that modify the grammar but preserve the language, improving the aesthetics of the final drawing.

Abstract: Graphs provide a visual means for examining relation data and force-directed methods are often used to lay out graphs for viewing. Making sense of a dynamic graph as it evolves over time is challenging, and previous force-directed methods were designed for static graphs. In this paper, we present an incremental version of a multilevel multi-pole layout method with a refinement scheme incorporated, which enables us to visualize online dynamic networks while maintaining a mental map of the graph structure. We demonstrate the effectiveness of our method and compare it to previous methods using several dynamic network data sets.

Abstract: 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 of the same page do not cross. In this paper, we approach the problem of determining whether a graph can be embedded in a book of a certain number of pages from a different perspective: We propose a simple and quite intuitive SAT formulation, which is robust enough to solve non-trivial instances of the problem in reasonable amount of time. In addition, we demonstrate how our approach helps to elaborate some hypotheses on the book embedding problem and develop new ones.

Abstract: A drawing of a graph G is radial if the vertices of G are placed on concentric circles C1, ... , Ck with common center c and edges are drawn radially: every edge crosses every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling.

We show that a graph G is radial planar if G has a radial drawing in which every
two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Tóth.

Abstract: In this paper we study the problem of designing a graph drawing algorithm for large graphs. The algorithm must be simple to implement and the computing infrastructure should not require major hardware or software investments. We describe a simple implementation of a spring embedder in Giraph, a vertex-centric open source framework for distributed computing. The algorithm is tested on real small-world, scale-free graphs of up to 1 million edges by using a cheap PaaS (Platform as a Service) infrastructure of Amazon. We can afford drawing graphs with about one million edges in about 20 minutes, by spending less than 2 USD per drawing for the cloud computing infrastructure.

Abstract: We consider arrangements of axis-aligned rectangles in the plane. A geometric arrangement specifies the coordinates of all rectangles, while a combinatorial arrangement specifies only the respective intersection type in which any two rectangles intersect, i.e., which corners of one rectangle are contained in the other rectangle and vice versa. First, we exclude two particular intersection types and investigate combinatorial rectangle arrangements with a triangle-free intersection graph. We show that such rectangle arrangements are in bijection with the 4-orientations of an underlying planar multigraph and prove that there is a corresponding geometric arrangement with only touching rectangles.
Moreover, we prove that every triangle-free planar graph is the contact graph of such an arrangement. Secondly, we study whether a given rectangle arrangement has a combinatorially equivalent square arrangement. In addition to some necessary conditions and counterexamples, we show that rectangle arrangements pierced by a horizontal line are squarable under certain sufficient conditions.

Abstract: We consider graphs which are partitioned into dense subgraphs. We introduce intersection-link representations for such graphs, in which each vertex u is represented by a geometric object R(u) and in which each edge (u,v) is represented by the intersection between R(u) and R(v) if it belongs to a dense subgraph or by a curve connecting the boundaries of R(u) and R(v) otherwise. We study a notion of planarity, called Clique Planarity, for intersection-link representations of graphs in which the dense subgraphs are cliques.

Abstract: The force-directed paradigm is one of the few generic approaches to drawing graphs. Since force-directed algorithms can be extended easily, they are used frequently. Most of these algorithms are, however, quite slow on large graphs as they compute a quadratic number of forces in each iteration. We speed up this computation by using an approximation based on the well-separated pair decomposition.
We perform experiments on a large number of graphs and show that we can strongly reduce the runtime—even on graphs with less then a hundred vertices—without a significant influence on the quality of the drawings (in terms of number of crossings and deviation in edge lengths).

Abstract: In this paper, we show that there exist (6t-1)-regular graphs with thickness t, by constructing such an example graph. Since all graphs of thickness t must have at least one node with degree less than 6t, this construction is optimal. We also show, by construction, that there exist 5t-regular graphs with geometric thickness at most t. Our construction for the latter builds off of a relationship between geometric thickness and the Cartesian product of two graphs.