Search

We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is 1-planar if every edge is crossed at most once. A 1-planar drawing is IC-planar if no two pairs of crossing edges share a vertex. A 1-planar drawing is NIC-planar if no two pairs of crossing edges share two vertices. We study the relations of these beyond-planar graph classes (beyond-planar graphs is a collective term for the primary attempts to generalize the planar graphs) to right-angle crossing (RAC) graphs that admit compact drawings on the grid with few bends. We present four drawing algorithms that preserve the given embeddings. First, we show that every n-vertex NIC-planar graph admits a NIC-planar RAC drawing with at most one bend per edge on a grid of size O ( n ) × O ( n ) . Then, we show that every n-vertex 1-planar graph admits a 1-planar RAC drawing with at most two bends per edge on a grid of size O ( n 3 ) × O ( n 3 ) . Finally, we make two known algorithms embedding-preserving; for drawing 1-planar RAC graphs with at most one bend per edge and for drawing IC-planar RAC graphs straight-line.

How to draw the vertices of a complete multipartite graph $G$ on different points of a bounded $d$-dimensional integer grid, such that the sum of squared distances between vertices of $G$ is (i) minimized or (ii) maximized? For both problems we provide a characterization of the solutions. For the particular case $d=1$, our solution for (i) also settles the minimum-2-sum problem for complete bipartite graphs; the minimum-2-sum problem was defined by Juvan and Mohar in 1992. Weighted centroidal Voronoi tessellations are the solution for (ii). Such drawings are related with Laplacian eigenvalues of graphs. This motivates us to study which properties of the algebraic connectivity of graphs carry over to the restricted setting of drawings of graphs with integer coordinates., Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018)

A straight-line grid drawing of a planar graph G of n vertices is a drawing of G on an integer grid such that each vertex is drawn as a grid point and each edge is drawn as a straight-line segment without edge crossings. Finding algorithms for straight-line grid drawings of maximal planar graphs (MPGs) in the minimum area is still an elusive goal. In this paper we explore the potential use of genetic algorithms to this problem and various implementation aspects related to it. Here we introduce a genetic algorithm, which nicely draws MPG of moderate size. This new algorithm draws these graphs in a rectangular grid with area ⌊ 2 ( n - 1 ) / 3 ⌋ × ⌊ 2 ( n - 1 ) / 3 ⌋ at least, and that this is optimal area (proved mathematically). Also, the novel issue in the proposed method is the fitness evaluation method, which is less costly than a standard fitness evaluation procedure. It is described, tested on several MPG.

Irreducible triangulations are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. Fusy proposed a straight-line grid drawing algorithm for irreducible triangulations, whose grid size is asymptotically with high probability 11n/27 × 11n/27 up to an additive error of [Formula: see text]. Later on, Fusy generalized the idea to quadrangulations and obtained a straight-line grid drawing, whose grid size is asymptotically with high probability 13n/27 × 13n/27 up to an additive error of [Formula: see text]. In this paper, we first prove that the above two straight-line grid drawing algorithms for irreducible triangulations and quadrangulations actually produce open rectangle-of-influence drawings for them respectively. Therefore, the above mentioned straight-line grid drawing size bounds also hold for the open rectangle-of-influence drawings. These results improve previous known drawing sizes.In the second part of the paper, we present another application of the results obtained by Fusy. We present a linear time algorithm for constructing a rectangular dual for a randomly generated irreducible triangulation with n vertices, one of its dimensions equals [Formula: see text] asymptotically with high probability, up to an additive error of [Formula: see text]. In addition, we prove that the one dimension tight bound for a rectangular dual of any irreducible triangulations with n vertices is (n + 1)/2.

Trees are usually drawn planar, i.e. without any crossings. In this paper, we investigate the area requirement of (non-upward) planar straight-line grid drawings of binary trees. Let T be a binary tree with n nodes. We show that T admits a planar straight-line grid drawing with area O(n) and with any pre-specified aspect ratio in the range [1,n α ], where a is a constant such that 0 < a < 1. We also show that such a drawing can be constructed in O(n log n) time.

An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bounding box. The first universal lower bound on the volume of threedimensional grid-drawings is obtained as a corollary. Our results generalise to the setting of multi-dimensional polyline grid-drawings.

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 very simple algorithm to find a grid drawing of any given 4-connected plane graph G with four or more vertices on the outer face. The algorithm takes time O(n) and yields a drawing in a rectangular grid of width \lceil n/2 \rceil - 1 and height \lfloor n/2\rfloor if G has n vertices. The algorithm is best possible in the sense that there are an infinite number of 4-connected plane graphs, any grid drawings of which need rectangular grids of width \lceil n/2 \rceil - 1 and height \lfloor n/2\rfloor .

Given a plane graph G, we wish to draw it in the plane in such a way that the vertices of G are represented as grid points, and the edges are represented as straight-line segments between their endpoints. An additional objective is to minimize the size of the resulting grid. It is known that each plane graph can be drawn in such a way in an (n - 2) x (n - 2) grid (for n >= 3), and that no grid smaller than (2n3 - 1) x (2n3 - 1) can be used for this purpose, if n is a multiple of 3. In fact, for all n >= 3, each dimension of the resulting grid needs to be at least @?2(n - 1)[email protected]?, even if the other one is allowed to be unbounded. In this paper we show that this bound is tight by presenting a grid drawing algorithm that produces drawings of width @?2(n - 1)[email protected]?. The height of the produced drawings is bounded by [email protected]?2(n - 1)[email protected]? - 1. Our algorithm runs in linear time and is easy to implement.

The rectangular grid drawing of a plane graph G is a drawing of G such that each vertex is located on a grid point, each edge is drawn as a horizontal or vertical line segment, and the contour of each face is drawn as a rectangle. In this paper we give a simple linear-time algorithm to find a rectangular grid drawing of G if it exists. We also give an upper bound W + H ≤ n2 on the sum of required width W and height H and a bound W H ≤ n216 on the area of a rectangular grid drawing of G, where n is the number of vertices in G. These bounds are best possible, and hold for any compact rectangular grid drawing.

A monotone drawing of a planar graph G is a planar straight-line drawing of G where a monotone path exists between every pair of vertices of G in some direction. Recently monotone drawings of planar graphs have been proposed as a new standard for visualizing graphs. A monotone drawing of a planar graph is a monotone grid drawing if every vertex in the drawing is drawn on a grid point. In this paper we study monotone grid drawings of planar graphs in a variable embedding setting. We show that every connected planar graph of n vertices has a monotone grid drawing on a grid of size O(n)×O(n 2), and such a drawing can be found in O(n) time. Our result immediately resolves two open problems on monotone drawings of planar graphs posted by Angelini et al.

We prove crossing number inequalities for geometric graphs whose vertex sets are taken from a d-dimensional grid of volume N and give applications of these inequalities to counting the number of non-crossing geometric graphs that can be drawn on such grids. In particular, we show that any geometric graph with m >= 8N edges and with vertices on a 3D integer grid of volume N, has \Omega((m^2/n)\log(m/n)) crossings. In d-dimensions, with d >= 4, this bound becomes \Omega(m^2/n). We provide matching upper bounds for all d. Finally, for d >= 4 the upper bound implies that the maximum number of crossing-free geometric graphs with vertices on some d-dimensional grid of volume N is n^\Theta(n). In 3 dimensions it remains open to improve the trivial bounds, namely, the 2^\Omega(n) lower bound and the n^O(n) upper bound., Comment: 16 pages, 3 figures; improved lower-bound in 3-D

A k-queue layout of a graph consists of a total order of the vertices, and a partition of the edges into k sets such that no two edges that are in the same set are nested with respect to the vertex ordering. A k-track layout of a graph consists of a vertex k-colouring, and a total order of each vertex colour class, such that between each pair of colour classes no two edges cross. The queue-number (track-number) of a graph G, is the minimum k such that G has a k-queue (k-track) layout. This paper proves that every n-vertex planar graph has track number and queue number at most O(log n). This improves the result of Di Battista, Frati and Pach [Foundations of Computer Science, (FOCS '10), pp. 365--374] who proved the first sub-polynomial bounds on the queue number and track number of planar graphs. Specifically, they obtained O(log^2 n) queue number and O(log^8 n) track number bounds for planar graphs. The result also implies that every planar graph has a 3D crossing-free grid drawing in O(n log n) volume. The proof uses a non-standard type of graph separators.

The class doughnut graphs is a subclass of 5-connected planar graphs. It is known that a doughnut graph admits a straight-line grid drawing with linear area, the outerplanarity of a doughnut graph is 3, and a doughnut graph is k-partitionable. In this paper we show that a doughnut graph exhibits a recursive structure. We also give an efficient algorithm for finding a shortest path between any pair of vertices in a doughnut graph. We also propose a nice application of a doughnut graph based on its properties.

We show that there exist series-parallel graphs requiring Ω(n2√log n) area in any straight-line or poly-line grid drawing, improving the previously best known Ω(n log n) lower bound.

The visualization of clustered graphs is a classical algorithmic topic that has several practical applications and is attracting increasing research interest. In this paper we deal with the visualization of clustered trees, a problem that is somehow foundational with respect to the one of visualizing a general clustered graph. We show many, in our opinion, surprising results that put in evidence how drawing clustered trees has many sharp differences with respect to drawing “plain” trees. We study a wide class of drawing standards, giving both negative and positive results. Namely, we show that there are clustered trees that do not have any drawing in certain standards and others that require exponential area. On the contrary, for many drawing conventions there are efficient algorithms that allow to draw clustered trees with polynomial asymptotically-optimal area. - The visualization of clustered graphs is a classical algorithmic topic that has several practical applications and is attracting increasing research interest. In this paper we deal with the visualization of clustered trees, a problem that is somehow foundational with respect to the one of visualizing a general clustered graph. We show many, in our opinion, surprising results that put in evidence how drawing clustered trees has many sharp differences with respect to drawing “plain” trees. We study a wide class of drawing standards, giving both negative and positive results. Namely, we show that there are clustered trees that do not have any drawing in certain standards and others that require exponential area. On the contrary, for many drawing conventions there are efficient algorithms that allow to draw clustered trees with polynomial asymptotically-optimal area.

We investigate open rectangle-of-influence drawings for irreducible triangulations, which are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. An open rectangle-of-influence drawing of a plane graph G is a type of straight-line grid drawing where there is no vertices drawn in the proper inside of the axis-parallel rectangle defined by the two end vertices of any edge. The algorithm presented by Miura and Nishizeki [8] uses a grid of size ${\cal W} + {\cal H} \leq$ (n-1) , where ${\cal W}$ is the width of the grid, ${\cal H}$ is the height of the grid and n is the number of vertices in G . Thus the area of the grid is at most ***(n-1)/2*** × $\lfloor$(n-1)/2$\rfloor$ [8]. In this paper, we prove that the two straight-line grid drawing algorithms for irreducible triangulations from [4] and quadrangulations from [3,5] actually produce open rectangle-of-influence drawings for them respectively. Therefore, the straight-line grid drawing size bounds from [3,4,5] also hold for the open rectangle-of-influence drawings. For irreducible triangulations, the new asymptotical grid size bound is $\emph{11n/27}$ × $\emph{11n/27}$. For quadrangulations, our asymptotical grid size bound $\emph{13n/27}$ × $\emph{13n/27}$ is the first known such bound.

We show that there exist series-parallel graphs requiring *** (n logn ) area in any straight-line or poly-line grid drawing. Such a result is achieved by proving that, in any straight-line or poly-line drawing of K 2,n , one side of the bounding box has length *** (n ).

We show that an outerplanar graph G with n vertices and degree d admits a planar straight-line grid drawing with area O(dn 1.48) in O(n) time. This implies that if d =o(n 0.52), then G can be drawn in this fashion in o(n 2) area.

Ordered trees are generally drawn using order-preserving planar straight-line grid drawings. We therefore investigate the area-requirements of such drawings, and present several results: Let T be an ordered tree with n nodes. Then: - T admits an order-preserving planar straight-line grid drawing with O(n log n) area. - If T is a binary tree, then T admits an order-preserving planar straight-line grid drawing with O(n log log n) area. - If T is a binary tree, then T admits an order-preserving upward planar straight-line grid drawing with optimal O(n log n) area. We also study the problem of drawing binary trees with user-specified arbitrary aspect ratios. We show that an ordered binary tree T with n nodes admits an order-preserving planar straight-line grid drawing Γ with width O(A + log n), height O((n/A) log A), and area O((A + log n)(n/A) log A) = O(n log n), where 2 ≤ A ≤ n is any user-specified number. Also note that all the drawings mentioned above can be constructed in O(n) time.

We prove that every n-vertex graph G with path-width pw(G) has a three-dimensional straight-line grid drawing with O(pw(G)2?n) volume. Thus for graphs with bounded path-width the volume is O(n), and it follows that for graphs with bounded tree-width, such as series-parallel graphs, the volume is O(n log2 n). No better bound than O(n2) was previously known for drawings of series-parallel graphs. For planar graphs we obtain three-dimensional drawings with O(n2) volume and O(?n) aspect ratio, whereas all previous constructions with O(n2) volume have ?(n) aspect ratio.

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 very simple algorithm to find a grid drawing of any given 4-connected plane graph G with four or more vertices on the outer face. The algorithm takes time O(n) and needs a rectangular grid of width ⌈n/2⌉-1 and height ⌈n/2⌉ if G has n vertices. The algorithm is best possible in the sense that there are an infinite number of 4-connected plane graphs any grid drawings of which need rectangular grids of width ⌈n/2⌉ - 1 and height ⌈n/⌉e.

A Fary grid drawing of a graph is a drawing on a three-dimensional grid such that vertices are placed at integer coordinates and edges are straight-lines such that no edge crossings are allowed.

Given a plane graph G, we wish to draw it in the plane, according to the given embedding, in such a way that the vertices of G are drawn as grid points, and the edges are drawn as straight-line segments between their endpoints. An additional objective is to minimize the size of the resulting grid. It is known that each plane graph can be drawn in such a way in a (n−2)×(n−2) grid (for n≥3), and that no grid smaller than (2n/3−1)×(2n/3−1) can be used for this purpose, if n is a multiple of 3. In fact, it can be shown that, for all n≥3, each dimension of the resulting grid needs to be at least [2(n−1)/3], even if the other one is allowed to be infinite. In this paper we show that this bound is tight, by presenting a grid drawing algorithm that produces drawings of width [2(n−1)/3]. The height of the produced drawings is bounded by 4[2(n−1)/3]−1.

In this paper, a technique of image processing for air vehicle and the method property of researching air vehicle using this technique is presented for the first time. In this method, the original data are obtained using several photographs of air vehicle and the three dimensional coordinates of air vehicle configuration are solved. After interpolating and surface smoothing, the grid drawing of air vehicle is made. The 3D image of air vehicle configuration is reconstructed using image processing techniques for this grid drawing. According to this 3D image, the wing area of air vehicle and other parameters are calculated, so the air dynamic property and flying property are researched. It is expressed through actual application for an aircraft that the air vehicle configuration can be obtained precisely using the method presented in this paper, so a very difficult problem is solved in this field.© (1993) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.