Drawing polytopal graphs with polymake

This note wants to explain how to obtain meaningful pictures of (possibly high-dimensional) convex polytopes, triangulated manifolds, and other objects from the realm of geometric combinatorics such as tight spans of finite metric spaces and tropical polytopes. In all our cases we arrive at specific, geometrically motivated, graph drawing problems. The methods displayed are implemented in the software system polymake.     

Drawing graphs with right angle crossings

Cognitive experiments show that humans can read graph drawings in which all edge crossings are at right angles equally well as they can read planar drawings; they also show that the readability of a drawing is heavily affected by the number of bends along the edges. A graph visualization whose edges can only cross perpendicularly is called a RAC (Right Angle Crossing) drawing. This paper initiates the study of combinatorial and algorithmic questions related to the problem of computing RAC drawings with few bends per edge. Namely, we study the interplay between number of bends per edge and total number of edges in RAC drawings. We establish upper and lower bounds on these quantities by considering two classical graph drawing scenarios: The one where the algorithm can choose the combinatorial embedding of the input graph and the one where this embedding is fixed.     

Drawing slicing graphs with face areas

We consider orthogonal drawings of a plane graph G$G$ with specified face areas. For a natural number k$k$, a k$k$-gonal drawing of G$G$ is an orthogonal drawing such that the boundary of G$G$ is drawn as a rectangle and each inner face is drawn as a polygon with at most k$k$ corners whose area is equal to the specified value. In this paper, we show that every slicing graph G$G$ with a slicing tree T$T$ and a set of specified face areas admits a 10-gonal drawing D$D$ such that the boundary of each slicing subgraph that appears in T$T$ is also drawn as a polygon with at most 10 corners. Such a drawing D$D$ can be found in linear time.     

Drawing layered graphs with port constraints

Complex software systems are often modeled using data flow diagrams, in which nodes are connected to each other through dedicated connection points called ports. The influence a layout algorithm has on the placement of ports is determined by port constraints defined on the corresponding node.In this paper we present approaches for integrating port constraints into the layer-based approach to graph drawing pioneered by Sugiyama et al. We show how our layout algorithm, called KLay Layered, progresses from relaxed to more restricted port constraint levels as it executes, and how established algorithms for crossing minimization and edge routing can be extended to support port constraints. Compared to the previous layout algorithms supporting ports, our algorithm produces fewer edge crossings and bends and yields pleasing results.We also explain and evaluate how layout algorithms can be kept simple by using the concept of intermediate processors to structure them in a modular way. A case study integrating our layout algorithm into UC Berkeley's Ptolemy tool illustrates how KLay Layered can be integrated into Java-based applications.     

Drawing directed graphs using quadratic programming

We describe a new method for visualization of directed graphs. The method combines constraint programming techniques with a high performance force-directed placement (FDP) algorithm. The resulting placements highlight hierarchy in directed graphs while retaining useful properties of FDP; such as emphasis of symmetries and preservation of proximity relations. Our algorithm automatically identifies those parts of the digraph that contain hierarchical information and draws them accordingly. Additionally, those parts that do not contain hierarchy are drawn at the same quality expected from a nonhierarchical, undirected layout algorithm. Our experiments show that this new approach is better able to convey the structure of large digraphs than the most widely used hierarchical graph-drawing method. An interesting application of our algorithm is directional multidimensional scaling (DMDS). DMDS deals with low-dimensional embedding of multivariate data where we want to emphasize the overall flow in the data (e.g., chronological progress) along one of the axes.     

Shortest noncrossing paths in plane graphs

Let G be an undirected plane graph with nonnegative edge length, and letk terminal pairs lie on two specified face boundaries. This paper presents an algorithm for findingk noncrossing paths inG, each connecting a terminal pair, and whose total length is minimum. Noncrossing paths may share common vertices or edges but do not cross each other in the plane. The algorithm runs in timeO(n logn) wheren is the number of vertices inG andk is an arbitrary integer.     

Drawing planar graphs using the canonical ordering

We introduce a new method to optimize the required area, minimum angle, and number of bends of planar graph drawings on a grid. The main tool is a new type of ordering on the vertices and faces of triconnected planar graphs. Using this method linear-time-and-space algorithms can be designed for many graph-drawing problems. Our main results are as follows:

Every triconnected planar graphG admits a planar convex grid drawing with straight lines on a (2n?4)×(n?2) grid, wheren is the number of vertices.

Every triconnected planar graph with maximum degree 4 admits a planar orthogonal grid drawing on ann×n grid with at most [3n/2]+4 bends, and ifn>6, then every edge has at most two bends.

Every planar graph with maximum degree 3 admits a planar orthogonal grid drawing with at most [n/2]+1 bends on an [n/2]×[n/2] grid.

Every triconnected planar graphG admits a planar polyline grid drawing on a (2n?6)×(3n?9) grid with minimum angle larger than 2/d radians and at most 5n?15 bends, withd the maximum degree.

These results give in some cases considerable improvements over previous results, and give new bounds in other cases. Several other results, e.g., concerning visibility representations, are included.     

Computing relative neighbourhood graphs in the plane

The relative neighbourhood graph (RNG) of a set of N points connects the relative neighbours, i.e. a pair of points is connected by an edge if those points are at least as close to each other as to any other point. The paper presents two new algorithms for constructing RNG in two-dimensional Euclidean space. The method is to determine a supergraph for RNG which can then be thinned efficiently from the extra edges. The first algorithm is simple, and works in O(N²) time. The worst case running time of the second algorithm is also O(N²), but its average case running time is O(N) for points from a homogeneous planar Poisson point process. Experimental tests have shown the usefulness of the approach.     

Drawing graphs by eigenvectors: theory and practice

The spectral approach for graph visualization computes the layout of a graph using certain eigenvectors of related matrices. Two important advantages of this approach are an ability to compute optimal layouts (according to specific requirements) and a very rapid computation time. In this paper, we explore spectral visualization techniques and study their properties from different points of view. We also suggest a novel algorithm for calculating spectral layouts resulting in an extremely fast computation by optimizing the layout within a small vector space.     

Drawing graphs with nonuniform nodes using potential fields

Graphs with nonuniform nodes arise naturally in many real-world applications. Although graph drawing has been a very active research in the computer science community during the past decade, most of the graph drawing algorithms developed thus far have been designed for graphs whose nodes are represented as single points. As a result, it is of importance to develop drawing methods for graphs whose nodes are of different sizes and shapes, in order to meet the need of real-world applications. To this end, a potential field approach, coupled with an idea commonly found in force-directed methods, is proposed in this paper for drawing graphs with nonuniform nodes in 2-D and 3-D. In our framework, nonuniform nodes are uniformly charged, while edges are modelled by springs. Using certain techniques developed in the field of potential-based path planning, we are able to find analytically tractable procedures for computing the repulsive force and torque of a node in the potential field induced by the remaining nodes. The crucial feature of our approach is that the rotation of every nonuniform node and the multiple edges between two nonuniform nodes are taken into account. In comparison with the existing algorithms found in the literature, our experimental results suggest this new approach to be promising, as drawings of good quality for a variety of moderate-sized graphs in 2-D and 3-D can be produced reasonably efficiently. That is, our approach is suitable for moderate-sized interactive graphs or larger-sized static graphs. Furthermore, to illustrate the usefulness of our new drawing method for graphs with zero-sized nodes, we give an application to the visualization of hierarchical clustered graphs, for which our method offers a very efficient solution.     

The complexity of drawing trees nicely

Summary We investigate the complexity of producing aesthetically pleasing drawings of binary trees, drawings that are as narrow as possible. The notion of what is aesthetically pleasing is embodied in several constraints on the placement of nodes, relative to other nodes. Among the results we give are: (1) There is no obvious principle of optimality that can be applied, since globally narrow, aesthetic placements of trees may require wider than necessary subtrees. (2) A previously suggested heuristic can produce drawings on n-node trees that are (n) times as wide as necessary. (3) The problem can be reduced in polynomial time to linear programming; hence, if the coordinates assigned to the nodes are continuous variables, then the problem can be solved in polynomial time. (4) If the placement is restricted to the integral lattice then the problem is NP-hard, as is its approximation to within a factor of about 4 per cent.This research was supported in part by the National Science Foundation, grant numbers NSF MCS 77-22830, NSF MCS 79-04897, and NSF MCS 81-17364     

A note on 2-facial coloring of plane graphs

An l-facial coloring of a plane graph is a vertex coloring such that any two different vertices joined by a facial walk of length at most l receive distinct colors. It is known that every plane graph admits a 2-facial coloring using 8 colors [D. Král, T. Madaras, R. Škrekovski, Cyclic, diagonal and facial coloring, European J. Combin. 3-4 (26) (2005) 473-490]. We improve this bound for plane graphs with large girth and prove that if G is a plane graph with girth g?14 (resp. 10, 8) then G admits a 2-facial coloring using 5 colors (resp. 6, 7). Moreover, we give exact bounds for outerplanar graphs and K₄-minor free graphs.     

Graphical condensation of plane graphs: A combinatorial approach

The method of graphical vertex-condensation for enumerating perfect matchings of plane bipartite graph was found by Propp [Generalized Domino-shuffling, Theoret. Comput. Sci. 303 (2003) 267–301], and was generalized by Kuo [Applications of graphical condensation for enumerating matchings and tilings, Theoret. Comput. Sci. 319 (2004) 29–57] and Yan and Zhang [Graphical condensation for enumerating perfect matchings, J. Combin. Theory Ser. A 110 (2005) 113–125]. In this paper, by a purely combinatorial method some explicit identities on graphical vertex-condensation for enumerating perfect matchings of plane graphs (which do not need to be bipartite) are obtained. As applications of our results, some results on graphical edge-condensation for enumerating perfect matchings are proved, and we count the sum of weights of perfect matchings of weighted Aztec diamond.     

Some results on acyclic edge coloring of plane graphs

An acyclic edge coloring of a graph is a proper edge coloring without bichromatic cycles. The acyclic chromatic index of a graph G, denoted by α^′(G), is the minimum number k such that G admits an acyclic edge coloring using k colors. Let G be a plane graph with maximum degree Δ and girth g. In this paper, we prove that α^′(G)=Δ(G) if one of the following conditions holds: (1) Δ?8 and g?7; (2) Δ?6 and g?8; (3) Δ?5 and g?9; (4) Δ?4 and g?10; (5) Δ?3 and g?14. We also improve slightly a result of A. Fiedorowicz et al. (2008) [7] by showing that every triangle-free plane graph admits an acyclic edge coloring using at most Δ(G)+5 colors.     

Visibility representation of plane graphs via canonical ordering tree

In a visibility representation (VR for short) of a plane graph G, each vertex of G is represented by a horizontal line segment such that the line segments representing any two adjacent vertices of G are joined by a vertical line segment. Rosenstiehl and Tarjan [Rectilinear planar layouts and bipolar orientations of planar graphs, Discrete Comput. Geom. 1 (1986) 343], Tamassia and Tollis [An unified approach to visibility representations of planar graphs, Discrete Comput. Geom. 1 (1986) 321] independently gave linear time VR algorithms for 2-connected plane graph. Afterwards, one of the main concerns for VR is the size of the representation. In this paper, we prove that any plane graph G has a VR with height bounded by . This improves the previously known bound . We also construct a plane graph G with n vertices where any VR of G requires a size of . Our result provides an answer to Kant's open question about whether there exists a plane graph G such that all of its VR require width greater that cn, where c>1 [G. Kant, A more compact visibility representation, Internat. J. Comput. Geom. Appl. 7 (1997) 197].     

On the complexity of drawing trees nicely: corrigendum

In this journal, Supowit and Reingold [1] have given a proof that it is NP-complete to decide whether a binary tree can be drawn on a grid with width 24 if certain æsthetic requirements are obeyed. We identify and repair a mistake in their proof.Received: 19 November 2003, Published online: 21 April 2004     

A quadratic identity for the number of perfect matchings of plane graphs

We present a quadratic identity on the number of perfect matchings of plane graphs by the method of graphical condensation, which generalizes the results found by Propp [J. Propp, Generalized domino-shuffling, Theoret. Comput. Sci. 303 (2003) 267–301], Kuo [E.H. Kuo, Applications of graphical condensation for enumerating matchings and tilings, Theoret. Comput. Sci. 319 (2004) 29–57], and Yan, Yeh, and Zhang [W.G. Yan, Y.-N. Yeh, F.J. Zhang, Graphical condensation of plane graphs: A combinatorial approach, Theoret. Comput. Sci. 349 (2005) 452–461].