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. [ABSTRACT FROM AUTHOR]

Abstract Dujmović et al. (2007) [6] showed that every 3-connected plane graph G with n vertices admits a straight-line drawing with at most 2.5 n − 3 segments, which is also the best known upper bound when restricted to plane triangulations. On the other hand, they showed that there exist triangulations requiring 2 n − 6 segments. In this paper we show that every plane triangulation admits a straight-line drawing with at most (7 n − 2 Δ 0 − 10) / 3 ≤ 2.33 n segments, where Δ 0 is the number of cyclic faces in the minimum realizer of G. For general plane graphs with n vertices and m edges, our algorithm requires at most (16 n − 3 m − 28) / 3 ≤ 5.33 n − m segments, which is less than 2.5 n − 3 for all m ≥ 2.84 n. In the context of grid drawings, where the vertices are restricted to have integer coordinates, we show that every triangulation with maximum degree D can be drawn with at most 2 n + t − 3 segments and O (8 t ⋅ D 2 t) area, where t is the minimum number of leaves over all the trees of the minimum realizer. This is the first nontrivial attempt to simultaneously optimize the area and the number of segments while drawing triangulations. These results extend to the case when the goal is to optimize the number of slopes in the drawing. [ABSTRACT FROM AUTHOR]

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 graphs have been discovered as a new standard for visualizing graphs. In this paper we study monotone drawings of series-parallel graphs in a variable embedding setting. We show that a series-parallel graph of n vertices has a straight-line planar monotone drawing on a grid of size O(n) × O(n2) and such a drawing can be found in linear time. [ABSTRACT FROM AUTHOR]

A convex drawing of a plane graph G is a plane drawing of G, where each vertex is drawn as a point, each edge is drawn as a straight line segment and each face is drawn as a convex polygon. A maximal segment is a drawing of a maximal set of edges that form a straight line segment. A minimum-segment convex drawing of G is a convex drawing of G where the number of maximal segments is the minimum among all possible convex drawings of G. In this paper, we present a linear-time algorithm to obtain a minimum-segment convex drawing Γ of a 3-connected cubic plane graph G of n vertices, where the drawing is not a grid drawing. We also give a linear-time algorithm to obtain a convex grid drawing of G on an $(\frac{n}{2}+1)\times(\frac {n}{2}+1)$ grid with at most s+1 maximal segments, where $s_{n}=\frac{n}{2}+3$ is the lower bound on the number of maximal segments in a convex drawing of G. [ABSTRACT FROM AUTHOR]

In a grid drawing of a planar graph, every vertex is located at a grid point, and every edge is drawn as a straight-line segment without any edge-intersection. It is known that every planar graph G of n vertices has a grid drawing on an ( n−2)×( n−2) or (4 n/3)×(2 n/3) integer grid. In this paper we show that if a planar graph G has a balanced partition then G has a grid drawing with small grid area. More precisely, if a separation pair bipartitions G into two edge-disjoint subgraphs G and G, then G has a max { n, n}×max { n, n} grid drawing, where n and n are the numbers of vertices in G and G, respectively. In particular, we show that every series-parallel graph G has a (2 n/3)×(2 n/3) grid drawing and a grid drawing with area smaller than 0.3941 n (<(2/3) n). [ABSTRACT FROM AUTHOR]

Abstract: Given two n-vertex plane graphs and with embedded in the grid, with straight-line segments as edges, we show that with a sequence of point moves (all point moves stay within a grid) and edge moves, we can transform the embedding of into the embedding of . In the case of n-vertex trees, we can perform the transformation with point and edge moves with all moves staying in the grid. We prove that this is optimal in the worst case as there exist pairs of trees that require point and edge moves. We also study the equivalent problems in the labeled setting. [Copyright &y& Elsevier]

Abstract: It is proved that every k-colourable graph on n vertices has a grid drawing with area, and that this bound is best possible. This result can be viewed as a generalisation of the no-three-in-line problem. A further area bound is established that includes the aspect ratio as a parameter. [Copyright &y& Elsevier]