A rectangle-of-influence drawing of a plane graph G is a straight-line planar drawing of G such that there is no vertex in the proper inside of the axis-parallel rectangle defined by the two ends of any edge. In this paper, we show that any given 5-connected plane graph G with five or more vertices on the outer face has a rectangle-of-influence drawing in an integer grid such that W + H ≤ n - 2, where n is the number of vertices in G, W is the width and H is the height of the grid.

In a convex grid drawing of a plane graph, all edges are drawn as straight-line segments without any edge-intersection, all vertices are put on grid points and all facial cycles are drawn as convex polygons. A plane graph G has a convex drawing if and only if G is internally triconnected, and an internally triconnected plane graph G has a convex grid drawing on an (n-1) × (n-1) grid if either G is triconnected or the triconnected component decomposition tree T(G) of G has two or three leaves, where n is the number of vertices in G. An internally triconnected plane graph G has a convex grid drawing on a 2n × 2n grid if T(G) has exactly four leaves. Furthermore, an internally triconnected plane graph G has a convex grid drawing on a 20n × 16n grid if T(G) has exactly five leaves. In this paper, we show that an internally triconnected plane graph G has a convex grid drawing on a 10n × 5n grid if T(G) has exactly five leaves. We also present a linear-time algorithm to find such a drawing.

Graph layout is a critical component in graph visualization. This paper proposes GRAPHULY, a graph u-nets-based neural network, for end-to-end graph layout generation. GRAPHULY learns the multi-level graph layout process and can generate graph layouts without iterative calculation. We also propose to use Laplacian positional encoding and a multi-level loss fusion strategy to improve the layout learning. We evaluate the model with a random dataset and a graph drawing dataset and showcase the effectiveness and efficiency of GRAPHULY in graph visualization.

A grid drawing of a plane graph G is a drawing of G on the plane so that all vertices of G are put on plane grid points and all edges are drawn as straight line segments between their endpoints without any edge-intersection. In this paper we give a linear-time algorithm to find a grid drawing of any given 5-connected plane graph G with five or more vertices on the outer face. The size of the drawing satisfies W + H≤n - 2, where n is the number of vertices in G, W is the width and H is the height of the grid drawing.

The Tokyo subway is one of the most complex subway networks in the world and it is difficult to compute a visually readable metro map using existing layout methods. In this paper, we present a new method that can generate complex metro maps such as the Tokyo subway network. Our method consists of two phases. The first phase generates rough metro maps. It decomposes the metro networks into smaller subgraphs and partially generates rough metro maps. In the second phase, we use a local search technique to improve the aesthetic quality of the rough metro maps. The experimental results including the Tokyo metro map are shown.

In a convex grid drawing of a plane graph, all edges are drawn as straight-line segments without any edge-intersection, all vertices are put on grid points and all facial cycles are drawn as convex polygons. A plane graph G has a convex drawing if and only if G is internally triconnected, and an internally triconnected plane graph G has a convex grid drawing on an (n-1)×(n-1) grid if either G is triconnected or the triconnected component decomposition tree T(G) of G has two or three leaves, where n is the number of vertices in G. An internally triconnected plane graph G has a convex grid drawing on a 2n×2n grid if T(G) has exactly four leaves. Furthermore, an internally triconnected plane graph G has a convex grid drawing on a 6n×n2 grid if T(G) has exactly five leaves. In this paper, we show that an internally triconnected plane graph G has a convex grid drawing on a 20n×16n grid if T(G) has exactly five leaves. We also present an algorithm to find such a drawing in linear time. This is the first algorithm that finds a convex grid drawing of such a plane graph G in a grid of O(n2) size.

Recent research on graph drawing focuses on Right-Angle-Crossing (RAC) drawings of 1-plane graphs, where each edge is drawn as a straight line and two crossing edges only intersect at right angles. We give a transformation from a restricted case of the RAC drawing problem to a problem of finding a straight-line drawing of a maximal plane graph where some angles are required to be acute. For a restricted version of the latter problem, we show necessary and sufficient conditions for such a drawing to exist, and design an O(n2)-time algorithm that given an n-vertex plane graph produces a desired drawing of the graph or reports that none exists.

In a convex drawing of a plane graph, all edges are drawn as straight-line segments without any edge-intersection and all facial cycles are drawn as convex polygons. In a convex grid drawing, all vertices are put on grid points. A plane graph G has a convex drawing if and only if G is internally triconnected, and an internally triconnected plane graph G has a convex grid drawing on an (n-1)×(n-1) grid if either G is triconnected or the triconnected component decomposition tree T(G) of G has two or three leaves, where n is the number of vertices in G. An internally triconnected plane graph G has a convex grid drawing on a 2n×2n grid if T(G) has exactly four leaves. In this paper, we show that an internally triconnected plane graph G has a convex grid drawing on a 6n×n2 grid if T(G) has exactly five leaves. We also present an algorithm to find such a drawing in linear time. This is the first algorithm that finds a convex grid drawing of such a plane graph G in a grid of polynomial size.

Hypergraphs drawn in the subset standard are useful to represent group relationships using topographic characteristics such as intersection, exclusion and enclosing. However, they present cluttering when dealing with a moderately high number of nodes (more than 20) and large hyperedges (connecting more than 10 nodes, with three or more overlapping nodes). At this complexity level, a study of the visual encoding of hypergraphs is required in order to reduce cluttering and increase the understanding of larger sets. Here we present a graph model and a visual design that help in the visualization of group relationships represented by hypergraphs. This is done by the use of superimposed visualization layers with different abstraction levels and the help of interaction and navigation through the display.

Because network diagrams drawn using the spring embedder are not easy to read, this paper proposes the use of "anchored maps" in which some nodes are fixed as anchors. The readability of network diagrams is discussed, anchored maps are proposed, and a method for drawing anchored maps is explained. The method uses indices to decide the orders of anchors because those orders markedly affect the readability of the network diagrams. Examples showing the effectiveness of the anchored maps are also shown.

A (k,2)-track layout of a graph G consists of a 2-track assignment of G and an edge k-coloring of G with no monochromatic X-crossing. This paper studies the problem of (k,2)-track layout of bipartite graph subdivisions. Recently V. Dujmovi and D.R. Wood showed that for every integer d ≥ 2, every graph G with n vertices has a (d+1,2)-track layout of a subdivision of G with 4 log d qn(G) +3 division vertices per edge, where qn(G) is the queue number of G. This paper improves their result for the case of bipartite graphs, and shows that for every integer d ≥ 2, every bipartite graph Gm,n has a (d+1,2)-track layout of a subdivision of Gm,n with 2 log d n -1 division vertices per edge, where m and n are numbers of vertices of the partite sets of Gm,n with m ≥ n.

In this paper, we present a novel force-directed method for automatically drawing intersecting compound mixed graphs (ICMGs) that can express complicated relations among elements such as adjacency, inclusion, and intersection. For this purpose, we take a strategy called unified simplification that can transform layout problem for an ICMG into that for an undirected graph. This method is useful for various information visualizations. We describe definitions, aesthetics, force model, algorithm, evaluation, and applications.

For an integer d > 0, a d-queue layout of a graph consists of a total order of the vertices, and a partition of the edges into d sets of non-nested edges with respect to the vertex ordering. Recently V. Dujmovi and D. R. Wood showed that for every integer d ≥ 2, every graph G has a d-queue layout of a subdivision of G with 2logd qn(G)+1 division vertices per edge, where qn(G) is the queue number of G. This paper improves the result for the case of a bipartite graph, and shows that for every integer d ≥ 2, every bipartite graph Gm,n has a d-queue layout of a subdivision of Gm,n with logd n-1 division vertices per edge, where m and n are numbers of vertices of the partite sets of Gm,n (m ≥ n).

A plane graph is a planar graph with a fixed embedding. In a no-bend orthogonal drawing of a plane graph, each vertex is drawn as a point and each edge is drawn as a single horizontal or vertical line segment. A planar graph is said to have a no-bend orthogonal drawing if at least one of its plane embeddings has a no-bend orthogonal drawing. In this paper we consider a class of planar graphs, called subdivisions of planar triconnected cubic graphs, and give a linear-time algorithm to examine whether such a planar graph G has a no-bend orthogonal drawing and to find one if G has.

Given a plane graph G, we wish to find a drawing of G in the plane such that the vertices of G are represented as grid points, and the edges are represented as straight-line segments between their endpoints without any edge-intersection. Such drawings are called planar straight-line drawings of G. An additional objective is to minimize the area of the rectangular grid in which G is drawn. In this paper first we review known two methods to find such drawings, then explain a hidden relation between them, and finally survey related results.

Concerning the complexity of tree drawing, the following result of Supowit and Reingold is known: the problem of minimum drawing binary trees under several constraints is NP-complete. There remain, however, many open problems. For example, is it still NP-complete if we eliminate some constraints from the above set? In this paper, we treat tree-structured diagrams. A tree-structured diagrm is a tree with variably sized rectangular nodes. We consider the layout problem of tree-structured diagrams on Z2 (the integral lattice). Our problems are different from that of Supowit and Reingold, even if our problems are limited to binary trees. In fact, our set of constraints and that of Supowit and Reingold are incomparable. We show that a problem is NP-complete under a certain set of constraints. Furthermore, we also show that another problem is still NP-complete, even if we delete a constraint concerning with the symmetry from the previous set of constraints. This constraint corresponds to one of the constraints of Supowit and Reingold, if the problem is limited to binary trees.