A Survey on Small-Area Planar Graph Drawing
---
paper_title: Drawing graphs: methods and models

paper_content:

Graph Drawing and Its Applications.- Drawing Planar Graphs.- Drawing Trees, Series-Parallel Digraphs, and Lattices.- Drawing on Physical Analogies.- Layered Drawings of Digraphs.- Orthogonal Graph Drawing.- 3D Graph Drawing.- Drawing Clusters and Hierarchies.- Dynamic Graph Drawing.- Map Labeling with Application to Graph Drawing.- Software Packages.
---
paper_title: On a Conjecture Related to Geometric Routing

paper_content:

We conjecture that any planar 3-connected graph can be embedded in the plane in such a way that for any nodes s and t, there is a path from s to t such that the Euclidean distance to t decreases monotonically along the path. A consequence of this conjecture would be that in any ad hoc network containing such a graph as a subgraph, 2-dimensional virtual coordinates for the nodes can be found for which greedy geographic routing is guaranteed to work. We discuss this conjecture and its equivalent forms. We show a weaker result, namely that for any network containing a 3-connected planar subgraph, 3-dimensional virtual coordinates always exist enabling a form of greedy routing inspired by the simplex method; we provide experimental evidence that this scheme is quite effective in practice. We also propose a rigorous form of face routing based on the Koebe-Andre’ev-Thurston theorem. Finally, we show a result delimiting the applicability of our approach: any 3-connected K 3,3-free graph has a planar 3-connected subgraph.
---
paper_title: Greedy drawings of triangulations

paper_content:

Greedy Routing is a class of routing algorithms in which the packets are forwarded in a manner that reduces the distance to the destination at every step. In an attempt to provide theoretical guarantees for a class of greedy routing algorithms, Papadimitriou and Ratajczak [19] came up with the following conjecture: Any 3-connected planar graph can be drawn in the plane such that for every pair of vertices s and t a distance decreasing path can be found. A path s = v1, v2,…,vk=t in a drawing is said to be distance decreasing if ||vi - t|| We settle this conjecture in the affirmative for the case of triangulations. A partitioning of the edges of a triangulation G into 3 trees, called the realizer of G, was first developed by Walter Schnyder who also gave a drawing algorithm based on this. We generalize Schnyder's algorithm to obtain a whole class of drawings of any given triangulation G. We show, using the Knaster-Kuratowski-Mazurkiewicz Theorem, that some drawing of G belonging to this class is greedy.
---
paper_title: Proximity Drawability: a Survey

paper_content:

Increasing attention has been given recently to drawings of graphs in which edges connect vertices based on some notion of proximity. Among such drawings are Gabriel, relative neighborhood, Delaunay, sphere of influence, and minimum spanning drawings. This paper attempts to survey the work that has been done to date on proximity drawings, along with some of the problems which remain open in this area.
---
paper_title: Polynomial area bounds for MST embeddings of trees

paper_content:

In their seminal paper on geometric minimum spanning trees, Monma and Suri (1992) [31] showed how to embed any tree of maximum degree 5 as a minimum spanning tree in the Euclidean plane. The embeddings provided by their algorithm require area O(2^n^^^2)xO(2^n^^^2) and the authors conjectured that an improvement below c^nxc^n is not possible, for some constant c>0. In this paper, we show how to construct MST embeddings of arbitrary trees of maximum degree 3 and 4 within polynomial area.
---
paper_title: Succinct Greedy Geometric Routing Using Hyperbolic Geometry

paper_content:

We describe a method for performing greedy geometric routing for any n-vertex simple connected graph G in the hyperbolic plane, so that a message M between any pair of vertices may be routed by having each vertex that receives M pass it to a neighbor that is closer to M's destination. Our algorithm produces succinct embeddings, where vertex positions are represented using O(\log n) bits and distance comparisons may be performed efficiently using these representations. These properties are useful, for example, for routing in sensor networks, where storage and bandwidth are limited.
---
paper_title: Proximity drawings in polynomial area and volume

paper_content:

We introduce a novel technique for drawing proximity graphs in polynomial area and volume. Previously known algorithms produce representations whose size increases exponentially with the size of the graph. This holds even when we restrict ourselves to binary trees. Our method is quite general and yields the first algorithms to construct (a) polynomial area weak Gabriel drawings of ternary trees, (b) polynomial area weak β-proximity drawing of binary trees for any 0 ≤ β < ∞ and (c) polynomial volume weak Gabriel drawings of unbounded degree trees. Notice that, in general, the above graphs do not admit a strong proximity drawing. Finally, we give evidence of the effectiveness of our technique by showing that a class of graph requiring exponential area even for weak Gabriel drawings, admits a linear-volume strong β-proximity drawing and a relative neighborhood drawing. All described algorithms run in linear time.
---
paper_title: The Strength of Weak Proximity

paper_content:

Abstract This paper studies weak proximity drawings of graphs and demonstrates their advantages over strong proximity drawings in certain cases. Weak proximity drawings are straight line drawings such that if the proximity region of two points p and q representing vertices is devoid of other points representing vertices, then segment ( p , q ) is allowed, but not forced, to appear in the drawing. This differs from the usual, strong, notion of proximity drawing in which such segments must appear in the drawing. Most previously studied proximity regions are associated with a parameter β , 0 ⩽ β ⩽ ∞ . For fixed β , weak β -drawability is at least as expressive as strong β -drawability, as a strong β -drawing is also a weak one. We give examples of graph families and β values where the two notions coincide, and a situation in which it is NP-hard to determine weak β -drawability. On the other hand, we give situations where weak proximity significantly increases the expressive power of β -drawability: we show that every graph has, for all sufficiently small β , a weak β -proximity drawing that is computable in linear time, and we show that every tree has, for every β less than 2, a weak β -drawing that is computable in linear time.
---
paper_title: Geographic routing without location information

paper_content:

For many years, scalable routing for wireless communication systems was a compelling but elusive goal. Recently, several routing algorithms that exploit geographic information (e.g. GPSR) have been proposed to achieve this goal. These algorithms refer to nodes by their location, not address, and use those coordinates to route greedily, when possible, towards the destination. However, there are many situations where location information is not available at the nodes, and so geographic methods cannot be used. In this paper we define a scalable coordinate-based routing algorithm that does not rely on location information, and thus can be used in a wide variety of ad hoc and sensornet environments.
---
paper_title: Geographic Routing Using Hyperbolic Space

paper_content:

We propose a scalable and reliable point-to-point routing algorithm for ad hoc wireless networks and sensor-nets. Our algorithm assigns to each node of the network a virtual coordinate in the hyperbolic plane, and performs greedy geographic routing with respect to these virtual coordinates. Unlike other proposed greedy routing algorithms based on virtual coordinates, our embedding guarantees that the greedy algorithm is always successful in finding a route to the destination, if such a route exists. We describe a distributed algorithm for computing each node's virtual coordinates in the hyperbolic plane, and for greedily routing packets to a destination point in the hyperbolic plane. (This destination may be the address of another node of the network, or it may be an address associated to a piece of content in a Distributed Hash Table. In the latter case we prove that the greedy routing strategy makes a consistent choice of the node responsible for the address, irrespective of the source address of the request.) We evaluate the resulting algorithm in terms of both path stretch and node congestion.
---
paper_title: Characterizing proximity trees

paper_content:

Complete characterizations are given for those trees that can be drawn as either the relative neighborhood graph, relatively closest graph, Gabriel graph, or modified Gabriel graph of a set of points in the plane. The characterizations give rise to linear-time algorithms for determining whether a tree has such a drawing; if such a drawing exists one can be constructed in linear time in the real RAM model. The characterization of Gabriel graphs settles several conjectures of Matula and Sokal [17].
---
paper_title: A near-linear area bound for drawing binary trees

paper_content:

AbstractWe present several simple methods to construct planar, strictly upward, strongly order-preserving, straight-line drawings of any n -node binary tree. In particular, it is shown that O(n1+ɛ) area is always sufficient for an arbitrary constant ɛ>0 .
---
paper_title: The logic engine and the realization problem for nearest neighbor graphs

paper_content:

Abstract Roughly speaking, a “nearest neighbor graph” is formed from a set of points in the plane by joining two points if one is the nearest neighbor of the other. There are several ways in which this intuitive concept can be made precise. This paper investigates the complexity of determining whether, for a given graph G , there is a set of points P in the plane such that G is isomorphic to a nearest neighbor graph on P . We show that this problem is NP-hard for several definitions of nearest neighbor graph. Our proof technique uses an interesting simulation of a mechanical device called a “logic engine”.
---
paper_title: An Algorithm to Construct Greedy Drawings of Triangulations

paper_content:

Note: Special Issue on Selected Papers from GD '08 Reference EPFL-ARTICLE-158714doi:10.7155/jgaa.00197 Record created on 2010-11-26, modified on 2017-07-08
---
paper_title: Succinct greedy drawings do not always exist

paper_content:

A greedy drawing is a graph drawing containing a distance-decreasing path for every pair of nodes. A path (v0,v1,…,vm) is distance-decreasing if d(vi,vm) < d(vi-1,vm), for i = 1,…,m. Greedy drawings easily support geographic greedy routing. Hence, a natural and practical problem is the one of constructing greedy drawings in the plane using few bits for representing vertex Cartesian coordinates and using the Euclidean distance as a metric. We show that there exist greedy-drawable graphs that do not admit any greedy drawing in which the Cartesian coordinates have less than a polynomial number of bits. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012 ::: ::: (A preliminary version of this article appeared at the International Symposium on Graph Drawing (GD '09).)
---
paper_title: Succinct Greedy Geometric Routing in the Euclidean Plane

paper_content:

In greedy geometric routing, messages are passed in a network embedded in a metric space according to the greedy strategy of always forwarding messages to nodes that are closer to the destination. We show that greedy geometric routing schemes exist for the Euclidean metric in R^2, for 3-connected planar graphs, with coordinates that can be represented succinctly, that is, with O(log n) bits, where n is the number of vertices in the graph. Moreover, our embedding strategy introduces a coordinate system for R^2 that supports distance comparisons using our succinct coordinates. Thus, our scheme can be used to significantly reduce bandwidth, space, and header size over other recently discovered greedy geometric routing implementations for R^2.
---
paper_title: Realizability of Delaunay triangulations

paper_content:

Abstract It is shown that any linear triangulation of a simple polygon can be realized as a (combinatorially equivalent) Delaunay triangulation. Simple examples are presented to show that neither complete triangulations of polygons nor triangulations without separating triangles are necessarily realizable as Delaunay triangulations.
---
paper_title: How to draw a planar graph on a grid

paper_content:

Answering a question of Rosenstiehl and Tarjan, we show that every plane graph withn vertices has a Fary embedding (i.e., straight-line embedding) on the 2n−4 byn−2 grid and provide anO(n) space,O(n logn) time algorithm to effect this embedding. The grid size is asymptotically optimal and it had been previously unknown whether one can always find a polynomial sized grid to support such an embedding. On the other hand we show that any setF, which can support a Fary embedding of every planar graph of sizen, has cardinality at leastn+(1−o(1))√n which settles a problem of Mohar.
---
paper_title: Convex Drawings of 3-Connected Plane Graphs

paper_content:

We use Schnyder woods of 3-connected planar graphs to produce convex straight-line drawings on a grid of size $(n-2-\Delta)\times (n-2-\Delta).$ The parameter $\Delta\geq 0$ depends on the Schnyder wood used for the drawing. This parameter is in the range $0 \leq \Delta\leq {n}/{2}-2.$ The algorithm is a refinement of the face-counting algorithm; thus, in particular, the size of the grid is at most $(f-2)\times(f-2).$ The above bound on the grid size simultaneously matches or improves all previously known bounds for convex drawings, in particular Schnyder's and the recent Zhang and He bound for triangulations and the Chrobak and Kant bound for 3-connected planar graphs. The algorithm takes linear time. The drawing algorithm has been implemented and tested. The expected grid size for the drawing of a random triangulation is close to $\frac{7}{8}n\times\frac{7}{8}n.$ For a random 3-connected plane graph, tests show that the expected size of the drawing is $\frac{3}{4}n\times\frac{3}{4}n.$
---
paper_title: Strictly convex drawings of planar graphs

paper_content:

Every three-connected planar graph with n vertices has a drawing on an O(n(2)) x O(n(2)) grid in which all faces are strictly convex polygons. These drawings are obtained by perturbing (not strictly) convex drawings on O(n) x O(n) grids. Tighter bounds are obtained when the faces have fewer sides. In the proof, we derive an explicit lower bound on the number of primitive vectors in a triangle.
---
paper_title: Planarity and Duality of Finite and Infinite Graphs

paper_content:

Abstract We present a short proof of the following theorems simultaneously: Kuratowski's theorem, Fary's theorem, and the theorem of Tutte that every 3-connected planar graph has a convex representation. We stress the importance of Kuratowski's theorem by showing how it implies a result of Tutte on planar representations with prescribed vertices on the same facial cycle as well as the planarity criteria of Whitney, MacLane, Tutte, and Fournier (in the case of Whitney's theorem and MacLane's theorem this has already been done by Tutte). In connection with Tutte's planarity criterion in terms of non-separating cycles we give a short proof of the result of Tutte that the induced non-separating cycles in a 3-connected graph generate the cycle space. We consider each of the above-mentioned planarity criteria for infinite graphs. Specifically, we prove that Tutte's condition in terms of overlap graphs is equivalent to Kuratowski's condition, we characterize completely the infinite graphs satisfying MacLane's condition and we prove that the 3-connected locally finite ones have convex representations. We investigate when an infinite graph has a dual graph and we settle this problem completely in the locally finite case. We show by examples that Tutte's criterion involving non-separating cycles has no immediate extension to infinite graphs, but we present some analogues of that criterion for special classes of infinite graphs.
---
paper_title: Output-Sensitive Reporting of Disjoint Paths

paper_content:

Abstract. A k -path query on a graph consists of computing k vertex-disjoint paths between two given vertices of the graph, whenever they exist. In this paper we study the problem of performing k -path queries, with ::: $ k \leq 3 $ , in a graph G with n vertices. We denote with ::: $ \ell $ the total length of the reported paths. For ::: $ k \leq 3 $ , we present an optimal data structure for G that uses O(n) space and executes k -path queries in output-sensitive ::: $ O(\ell) $ time. For triconnected planar graphs, our results make use of a new combinatorial structure that plays the same role as bipolar (st ) orientations for biconnected planar graphs. This combinatorial structure also yields an alternative construction of convex grid drawings of triconnected planar graphs.
---
paper_title: Universality considerations in VLSI circuits

paper_content:

The problem of embedding the interconnection pattern of a circuit into a two-dimensional surface of minimal area is discussed. Since even for some natural patterns graphs containing m connections may require Ω(m2) area, in order to achieve compact embeddings restricted classes of graphs have to be considered. For example, arbitrary trees (of bounded degree) can be embedded in linear area without edges crossing over. Planar graphs can be embedded efficiently only if crossovers are allowed in the embedding.
---
paper_title: Embedding planar graphs on the grid

paper_content:

We show that each plane graph of order n 2 3 has a straight line embedding on the n-2 by n-2 grid. This embedding is computable in time O(n). A nice feature of the vertex-coordinates is that they have a purely combinatorial meaning.
---
paper_title: Convex Grid Drawings of 3-Connected Planar Graphs

paper_content:

We consider the problem of embedding the vertices of a plane graph into a small (polynomial size) grid in the plane in such a way that the edges are straight, nonintersecting line segments and faces are convex polygons. We present a linear-time algorithm which, given an n-vertex 3-connected plane G (with n ≥ 3), finds such a straight-line convex embedding of G into a (n - 2) × (n - 2) grid.
---
paper_title: On the Number of Convex Lattice Polygons

paper_content:

Note: Professor Pach's number: [093] Reference DCG-ARTICLE-2008-017doi:10.1017/S0963548300000341 Record created on 2008-11-17, modified on 2017-05-12
---
paper_title: A note on minimum-area straight-line drawings of planar graphs

paper_content:

Despite a long research effort, finding the minimum area for straight-line grid drawings of planar graphs is still an elusive goal. A long-standing lower bound on the area requirement for straight-line drawings of plane graphs was established in 1984 by Dolev, Leighton, and Trickey, who exhibited a family of graphs, known as nested triangles graphs, for which (2n/3 - 1) × (2n/3 - 1) area is necessary. We show that nested triangles graphs can be drawn in 2n2/9 + O(n) area when the outer face is not given, improving a previous n2/3 area upper bound. Further, we show that n2/9 + Ω(n) area is necessary for any planar straight-line drawing of a nested triangles graph. Finally, we deepen our insight into the 4/9n2-4/3n+1 lower bound by Dolev, Leighton, and Trickey, which is conjectured to be tight, showing a family of plane graphs requiring more area.
---
paper_title: Drawing planar graphs using the canonical ordering

paper_content:

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.
---
paper_title: HOW TO DRAW A Graph

paper_content:

W E use the definitions of (11). However, in deference to some recent attempts to unify the terminology of graph theory we replace the term 'circuit' by 'polygon', and 'degree' by 'valency'. A graph G is 3-connected (nodally 3-connected) if it is simple and non-separable and satisfies the following condition; if G is the union of two proper subgraphs H and K such that HnK consists solely of two vertices u and v, then one of H and K is a link-graph (arc-graph) with ends u and v. It should be noted that the union of two proper subgraphs H and K of G can be the whole of G only if each of H and K includes at least one edge or vertex not belonging to the other. In this paper we are concerned mainly with nodally 3-connected graphs, but a specialization to 3-connected graphs is made in § 12. In § 3 we discuss conditions for a nodally 3-connected graph to be planar, and in § 5 we discuss conditions for the existence of Kuratowski subgraphs of a given graph. In §§ 6-9 we show how to obtain a convex representation of a nodally 3-connected graph, without Kuratowski subgraphs, by solving a set of linear equations. Some extensions of these results to general graphs, with a proof of Kuratowski's theorem, are given in §§ 10-11. In § 12 we discuss the representation in the plane of a pair of dual graphs, and in § 13 we draw attention to some unsolved problems.
---
paper_title: Minimum-Area Drawings of Plane 3-Trees

paper_content:

A straight-line grid drawing of a plane graph G is a planar drawing of G, where each vertex is drawn at a grid point of an integer grid and each edge is drawn as a straight-line segment. The area of such a drawing is the area of the smallest axis-aligned rectangle on the grid which encloses the drawing. A minimum-area drawing of a plane graph G is a straight-line grid drawing of G where the area of the drawing is the minimum. Although it is NP-hard to find minimum-area drawings for general plane graphs, in this paper we obtain minimumarea drawings for plane 3-trees in polynomial time. Furthermore, we show a ⌊ 2n 3 − 1⌋ × 2⌈ n 3 ⌉ lower bound for the area of a straight-line grid drawing of a plane 3tree with n ≥ 6 vertices, which improves the previously known lower bound ⌊ 2(n−1) 3 ⌋×⌊ 2(n−1) 3 ⌋ for plane graphs.
---
paper_title: A Linear-time Algorithm for Drawing a Planar Graph on a Grid

paper_content:

Abstract We present a linear-time algorithm that, given an n -vertex planar graph G , finds an embedding of G into a (2 n − 4) × ( n − 2) grid such that the edges of G are straight-line segments.
---
paper_title: How to draw a planar graph on a grid

paper_content:

Answering a question of Rosenstiehl and Tarjan, we show that every plane graph withn vertices has a Fary embedding (i.e., straight-line embedding) on the 2n−4 byn−2 grid and provide anO(n) space,O(n logn) time algorithm to effect this embedding. The grid size is asymptotically optimal and it had been previously unknown whether one can always find a polynomial sized grid to support such an embedding. On the other hand we show that any setF, which can support a Fary embedding of every planar graph of sizen, has cardinality at leastn+(1−o(1))√n which settles a problem of Mohar.
---
paper_title: Drawing planar graphs

paper_content:

Given a planar graph, we wish to draw it in the plane so that no edges cross. We might be given a particular planarisation (a specification giving the faces of the desired drawing) instead of merely the graph, but this is not required. Given a planarisation and a choice of outermost face, all drawings are in a sense equivalent; indeed, when the drawing is performed on the surface of a sphere instead of on the plane, even the choice of outermost face is irrelevant. To make the problem meaningful, we must introduce further constraints. Two general forms of constraints are: (1) absolute restrictions on the details of the drawing, that is, disallowing or requiring certain features, and (2) weighted restrictions, that is, additional objectives to be met to whatever extent is possible. ::: We first examine the general problem, and look at various constraints that have been found to yield useful drawings in some applications. We then examine in more detail one particular set of constraints, developing a fast algorithm for producing drawings meeting those constraints, and proving some theorems relating to the overall complexity of the problem. Finally, we look at what results are known regarding other variations on the general problem.
---
paper_title: Planar Polyline Drawings with Good Angular Resolution

paper_content:

We present a linear time algorithm that constructs a planar polyline grid drawing of any plane graph with n vertices and maximum degree n on a (2n - 5) × (3/2n - 7/2) grid with at most 5n - 15 bends and minimum angle > 2/d. In the constructed drawings, every edge has at most three bends and length O(n). To our best knowledge, this algorithm achieves the best simultaneous bounds concerning the grid size, angular resolution, and number of bends for planar grid drawings of high-degree planar graphs. Besides the nice theoretical features, the practical drawings are aesthetically very pleasing. An implementation of our algorithm is available with the AGD-Library (Algorithms for Graph Drawing) [2, 1]. Our algorithm is based on ideas by Kant for polyline grid drawings for triconnected plane graphs [23]. In particular, our algorithm significantly improves upon his bounds on the angular resolution and the grid size for non-triconnected plane graphs. In this case, Kant could show an angular resolution of 4/3d+7 and a grid size of (2n - 5) × (3n - 6), only.
---
paper_title: A Framework for Drawing Planar Graphs with Curves and Polylines

paper_content:

We describe a unified framework of aesthetic criteria and complexity measures for drawing planar graphs with polylines and curves. This framework includes several visual properties of such drawings, including aspect ratio, vertex resolution, edge length, edge separation, and edge curvature, as well as complexity measures such as vertex and edge representational complexity and the area of the drawing. In addition to this general framework, we present algorithms that operate within this framework. Specifically, we describe an algorithm for drawing any n- vertex planar graph in an O(n) × O(n) grid using polylines that have at most two bends per edge and asymptotically-optimal worst-case angular resolution. More significantly, we show how to adapt this algorithm to draw any n-vertex planar graph using cubic Bezier curves, with all vertices and control points placed within an O(n) × O(n) integer grid so that the curved edges achieve a curvilinear analogue of good angular resolution. All of our algorithms run in O(n) time.
---
paper_title: On planar polyline drawings

paper_content:

We present a linear time algorithm that produces a planar polyline drawing for a plane graph with n vertices in a grid of size bounded by (p + 1) × (n - 2), where p ≤ (⌊2n-5/3⌋). It uses at most p ≤ ⌊2n-5/3⌋ bends, and each edge uses at most one bend. Compared with the area optimal polyline drawing algorithm in [3], our algorithm uses a larger grid size bound in trade for a smaller bound on the total number of bends. Their bend bound is (n-2). Our algorithm is based on a transformation from Schnyder's realizers [6,7] of maximal plane graphs to transversal structures [4,5] for maximal internally 4-connected plane graphs. This transformation reveals important relations between the two combinatorial structures for plane graphs, which is of independent interest.
---
paper_title: Universality considerations in VLSI circuits

paper_content:

The problem of embedding the interconnection pattern of a circuit into a two-dimensional surface of minimal area is discussed. Since even for some natural patterns graphs containing m connections may require Ω(m2) area, in order to achieve compact embeddings restricted classes of graphs have to be considered. For example, arbitrary trees (of bounded degree) can be embedded in linear area without edges crossing over. Planar graphs can be embedded efficiently only if crossovers are allowed in the embedding.
---
paper_title: Drawing Planar Graphs with Circular Arcs

paper_content:

In this paper we address the problem of drawing planar graphs with circular arcs while maintaining good angular resolution and small drawing area. We present a lower bound on the area of drawings in which edges are drawn using exactly one circular arc. We also give an algorithm for drawing n-vertex planar graphs such that the edges are sequences of two continuous circular arcs. The algorithm runs in O(n) time and embeds the graph on the O(n) × O(n) grid, while maintaining ?(1/d(v)) angular resolution, where d(v) is the degree of vertex v. Since in this case we use circular arcs of infinite radius, this is also the first algorithm that simultaneously achieves good angular resolution, small area, and at most one bend per edge using straight-line segments. Finally, we show how to create drawings in which edges are smooth C1-continuous curves, represented by a sequence of at most three circular arcs.
---
paper_title: Embedding planar graphs on the grid

paper_content:

We show that each plane graph of order n 2 3 has a straight line embedding on the n-2 by n-2 grid. This embedding is computable in time O(n). A nice feature of the vertex-coordinates is that they have a purely combinatorial meaning.
---
paper_title: Planar Polyline Drawings via Graph Transformations

paper_content:

We study the problem of transforming plane triangulations into irreducible triangulations, which are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. Our linear time transformation reveals important relations between the minimum Schnyder’s realizers of plane triangulations (Bonichon et al., Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2607, pp. 499–510, Springer, Berlin, 2003; Research Report RR-1279-02, LaBRI, University of Bordeaux, France; Brehm, Diploma thesis, FB Mathematik und Informatik, Freie Universitat Berlin, 2000) and the transversal structures of irreducible triangulations (Fusy, Proceedings of 13th International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 3843, pp. 177–188, Springer, Berlin, 2005; He, SIAM J. Comput. 22:1218–1226, 1993). The transformation morphs a 3-connected plane graph into an internally 4-connected plane graph. Therefore some of the graph algorithms designed specifically for 4-connected plane graphs can be applied to 3-connected plane graphs indirectly. As an example of such applications, we present a linear time algorithm that produces a planar polyline drawing for a plane graph with n vertices in a grid of size bounded by W×H, where $W\leq\lfloor\frac{2n-2}{3}\rfloor$, and $W+H\leq\lfloor \frac{4n-4}{3}\rfloor$. It uses at most $\lfloor\frac{2n-5}{3}\rfloor$bends, and each edge uses at most one bend. Our algorithm is area optimal. Compared with the existing area optimal polyline drawing algorithm proposed in Bonichon et al. (Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 2573, pp. 35–46, Springer, Berlin, 2002), our algorithm uses a smaller number of bends. Their bend bound is (n−2).
---
paper_title: Wagner's Theorem on Realizers

paper_content:

A realizer of a maximal plane graph is a set of three particular spanning trees. It has been used in several graph algorithms and particularly in graph drawing algorithms. We propose colored flips on realizers to generalize Wagner's theorem on maximal planar graphs to realizers. From this result, it is proved that ?0 + ?1 + ?2 - ? = ni is the number of inner nodes in the tree Ti, ? is the number of three colored faces in the realizer and n is the number of vertices. As an application of this formula, we show that orderly spanning trees with at most ? 2n+1-?/3 ? leaves can be computed in linear time.
---
paper_title: Small sets supporting fary embeddings of planar graphs

paper_content:

Answering a question of Rosenstiehl and Tarjan, we show that every plane graph with n vertices has a Fary embedding (i.e., straight-line embedding) on the 2 n - 4 by n - 2 grid and provide an O( n ) space, O( n log n ) time algorithm to effect this embedding. The grid size is asymptotically optimal and it had been previously unknown whether one can always find a polynomial sized grid to support such an embedding. On the other hand we show that any set F , which can support a Fary embedding of every planar graph of size n , has cardinality at least n + (1 - o (1)) √ n which settles a problem of Mohar.
---
paper_title: How to draw a planar graph on a grid

paper_content:

Answering a question of Rosenstiehl and Tarjan, we show that every plane graph withn vertices has a Fary embedding (i.e., straight-line embedding) on the 2n−4 byn−2 grid and provide anO(n) space,O(n logn) time algorithm to effect this embedding. The grid size is asymptotically optimal and it had been previously unknown whether one can always find a polynomial sized grid to support such an embedding. On the other hand we show that any setF, which can support a Fary embedding of every planar graph of sizen, has cardinality at leastn+(1−o(1))√n which settles a problem of Mohar.
---
paper_title: Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems

paper_content:

Abstract In this paper we extend the concept of the regular edge labeling for general plane graphs and for triconnected triangulated plane graphs to 4-connected triangulated plane graphs. We present two different linear time algorithms for constructing such a labeling. By using regular edge labeling, we present a new linear time algorithm for constructing rectangular dual of planar graphs. Our algorithm is simpler than previously known algorithms. The coordinates of the rectangular dual constructed by our algorithm are integers, while the one constructed by known algorithms are real numbers. Our second regular edge labeling algorithm is based on canonical ordering of 4-connected triangulated plane graphs. By using this technique, we present a new algorithm for constructing visibility representation of 4-connected planar graphs. Our algorithm reduces the size of the representation by a factor of 2 for such graphs.
---
paper_title: Grid Embedding of 4-Connected Plane Graphs

paper_content:

A straight line grid embedding of a plane graph G is a drawing of G such that the vertices are drawn at grid points and the edges are drawn as non-intersecting straight line segments. In this paper, we show that, if a 4-connected plane graph G has at least 4 vertices on its exterior face, then G can be embedded on a grid of size W×H such that W+H≤n, W≤(n+3)/2 and H≤2(n−1)/3, where n is the number of vertices of G. Such an embedding can be computed in linear time.
---
paper_title: Grid Drawings of 4-Connected Plane Graphs

paper_content:

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 .
---
paper_title: On Triangulating Planar Graphs under the Four-Connectivity Constraint

paper_content:

Abstract. Triangulation of planar graphs under constraints is a fundamental problem in the representation of objects. Related keywords are graph augmentation from the field of graph algorithms and mesh generation from the field of computational geometry. We consider the triangulation problem for planar graphs under the constraint to satisfy 4-connectivity. A 4-connected planar graph has no separating triangles, i.e., cycles of length 3 which are not a face. We show that triangulating embedded planar graphs without introducing new separating triangles can be solved in linear time and space. If the initial graph had no separating triangle, the resulting triangulation is 4-connected. If the planar graph is not embedded, then deciding whether there exists an embedding with at most k separating triangles is NP-complete. For biconnected graphs a linear-time approximation which produces an embedding with at most twice the optimal number is presented. With this algorithm we can check in linear time whether a biconnected planar graph can be made 4-connected while maintaining planarity. Several related remarks and results are included.
---
paper_title: Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions

paper_content:

This paper investigates the following question: Given an in- teger grid φ, where φ is a proper subset of the integer plane or a proper subset of the integer 3d space, which graphs admit straight-line crossing- free drawings with vertices located at the grid points of φ? We charac- terize the trees that can be drawn on a two dimensional c · n × k grid, where k and c are given integer constants, and on a two dimensional grid consisting of k parallel horizontal lines of infinite length. Motivated by the results on the plane we investigate restrictions of the integer grid in 3 dimensions and show that every outerplanar graph with n vertices can be drawn crossing-free with straight lines in linear volume on a grid called a prism. This prism consists of 3n integer grid points and is universal - it supports all outerplanar graphs of n vertices. This is the first algorithm that computes crossing-free straight line 3d drawings in linear volume for a non-trivial family of planar graphs. We also show that there exist planar graphs that cannot be drawn on the prism and that the extension to a n × 2 × 2 integer grid, called a box, does not admit the entire class of planar graphs.
---
paper_title: Small Drawings of Outerplanar Graphs, Series-Parallel Graphs, and Other Planar Graphs

paper_content:

In this paper, we study small planar drawings of planar graphs. For arbitrary planar graphs, Θ(n 2) is the established upper and lower bound on the worst-case area. A long-standing open problem is to determine for what graphs a smaller area can be achieved. We show here that series-parallel graphs can be drawn in O(n 3/2) area, and outerplanar graphs can be drawn in O(nlog n) area, but 2-outerplanar graphs and planar graphs of proper pathwidth 3 require Ω(n 2) area. Our drawings are visibility representations, which can be converted to polyline drawings of asymptotically the same area.
---
paper_title: Drawing Outer-Planar Graphs in O(n log n) Area

paper_content:

In this paper, we study drawings of outer-planar graphs in various models. We show that O(n log n) area can be achieved for such drawings if edges are allowed to have bends or if vertices may be represented by boxes. The question of straight-line grid-drawings of outer-planar graphs in o(n 2 ) area remains open.
---
paper_title: Lower Bounds on the Area Requirements of Series-Parallel Graphs

paper_content:

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 ).
---
paper_title: Drawing Outer-Planar Graphs in O(n log n) Area

paper_content:

In this paper, we study drawings of outer-planar graphs in various models. We show that O(n log n) area can be achieved for such drawings if edges are allowed to have bends or if vertices may be represented by boxes. The question of straight-line grid-drawings of outer-planar graphs in o(n 2 ) area remains open.
---
paper_title: A near-linear area bound for drawing binary trees

paper_content:

AbstractWe present several simple methods to construct planar, strictly upward, strongly order-preserving, straight-line drawings of any n -node binary tree. In particular, it is shown that O(n1+ɛ) area is always sufficient for an arbitrary constant ɛ>0 .
---
paper_title: Small area drawings of outerplanar graphs

paper_content:

We show three linear time algorithms for constructing planar straight-line grid drawings of outerplanar graphs. The first and the second algorithm are for balanced outerplanar graphs. Both require linear area. The drawings produced by the first algorithm are not outerplanar while those produced by the second algorithm are. On the other hand, the first algorithm constructs drawings with better angular resolution. The third algorithm constructs outerplanar drawings of general outerplanar graphs with O(n1.48) area. Further, we study the interplay between the area requirements of the drawings of an outerplanar graph and the area requirements of a special class of drawings of its dual tree.
---
paper_title: Area-efficient planar straight-line drawings of outerplanar graphs

paper_content:

It is important to minimize the area of a drawing of a graph, so that the drawing can fit in a small drawing-space. It is well-known that a planar graph with n vertices admits a planar straight-line grid drawing with O(n^2) area [H. de Fraysseix, J. Pach, R. Pollack, How to draw a planar graph on a grid, Combinatorica 10(1) (1990) 41-51; W. Schnyder, Embedding planar graphs on the grid, in: Proceedings of the First ACM-SIAM Symposium on Discrete Algorithms, 1990, pp. 138-148]. Unfortunately, there is a matching lower-bound of @W(n^2) on the area-requirements of the planar straight-line grid drawings of certain planar graphs. Hence, it is important to investigate important categories of planar graphs to determine if they admit planar straight-line grid drawings with o(n^2) area. In this paper, we investigate an important category of planar graphs, namely, outerplanar graphs. We show that an outerplanar graph G with degree d admits a planar straight-line grid drawing with area O(dn^1^.^4^8) in O(n) time. This implies that if d=o(n^0^.^5^2), then G can be drawn in this manner in o(n^2) area.
---
paper_title: Straight-Line Drawings of General Trees with Linear Area and Arbitrary Aspect Ratio

paper_content:

Trees are usually drawn planar, i.e. without any crossings. In this paper we investigate the area requirement of planar straight-line drawings of trees. A degree-d tree is one in which each node has at most d edges incident on it. Let T be a degree-d tree with n nodes, such that d = O(nδ), where δ < 1/2 is a constant. We show that T admits a planar straight-line grid drawing with area O(n) and with any prespecified aspect ratio in the range [1, nα], where α is a constant such that 0 ≤ α < 1. We also show that such a drawing can be constructed in O(n log n) time.
---
paper_title: Universality considerations in VLSI circuits

paper_content:

The problem of embedding the interconnection pattern of a circuit into a two-dimensional surface of minimal area is discussed. Since even for some natural patterns graphs containing m connections may require Ω(m2) area, in order to achieve compact embeddings restricted classes of graphs have to be considered. For example, arbitrary trees (of bounded degree) can be embedded in linear area without edges crossing over. Planar graphs can be embedded efficiently only if crossovers are allowed in the embedding.
---
paper_title: Straight-line Drawings of Binary Trees with Linear Area and Arbitrary Aspect Ratio

paper_content:

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.
---
paper_title: A note on optimal area algorithms for upward drawings of binary trees

paper_content:

Abstract The goal of this paper is to investigate the area requirements for upward grid drawings of binary trees. First, we show that there is a family of binary trees with n vertices that require ω(n log n) area; this bound is tight to within a constant factor, i.e. any binary tree with n vertices can be drawn in O(n log n) area. Then we present an algorithm for constructing an upward drawing of a complete binary tree with n vertices in O(n) area, and, finally, we extend this result to the drawings of Fibonacci trees.
---
paper_title: Area-efficient algorithms for straight-line tree drawings

paper_content:

Abstract We investigate several straight-line drawing problems for bounded-degree trees in the integer grid without edge crossings under various types of drawings: (1) upward drawings whose edges are drawn as vertically monotone chains, a sequence of line segments, from a parent to its children, (2) order-preserving drawings which preserve the left-to-right order of the children of each vertex, and (3) orthogonal straight-line drawings in which each edge is represented as a single vertical or horizontal segment. Main contribution of this paper is a unified framework to reduce the upper bound on area for the straight-line drawing problems from O (n log n) (Crescenzi et al., 1992) to O (n loglog n) . This is the first solution of an open problem stated by Garg et al. (1993). We also show that any binary tree admits a small area drawing satisfying any given aspect ratio in the orthogonal straight-line drawing type. Our results are briefly summarized as follows. Let T be a bounded-degree tree with n vertices. Firstly, we show that T admits an upward straight-line drawing with area O (n loglog n) . If T is binary, we can obtain an O (n loglog n) -area upward orthogonal drawing in which each edge is drawn as a chain of at most two orthogonal segments and which has O (n/ log n) bends in total. Secondly, we present O (n loglog n) -area (respectively, -volume) orthogonal straight-line drawing algorithms for binary trees with arbitrary aspect ratios in 2-dimension (respectively, 3-dimension). Finally, we present some experimental results which shows the area requirements, in practice, for (order-preserving) upward drawing are much smaller than theoretical bounds obtained through analysis.
---
paper_title: A note on optimal area algorithms for upward drawings of binary trees

paper_content:

Abstract The goal of this paper is to investigate the area requirements for upward grid drawings of binary trees. First, we show that there is a family of binary trees with n vertices that require ω(n log n) area; this bound is tight to within a constant factor, i.e. any binary tree with n vertices can be drawn in O(n log n) area. Then we present an algorithm for constructing an upward drawing of a complete binary tree with n vertices in O(n) area, and, finally, we extend this result to the drawings of Fibonacci trees.
---
paper_title: Optimizing area and aspect ratio in straight-line orthogonal tree drawings

paper_content:

We investigate the problem of drawing an arbitrary n-node binary tree orthogonally and upwardly in an integer grid using straight-line edges. We show that one can simultaneously achieve good area bounds while also allowing the aspect ratio to be chosen as a fixed constant or a parameter under the user's control. In addition, we show that one can also achieve an additional desirable aesthetic criterion, which we call "subtree separation". Our drawings require O(n logn) area, which we show is optimal to within constant factors in the worst case (i.e. there are trees that need Ω(n logn) area for any upward orthogonal straight-line drawing with good aspect ratio). An improvement for non-upward drawings is briefly mentioned.
---
paper_title: Area-efficient order-preserving planar straight-line drawings of ordered trees

paper_content:

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.
---
paper_title: A note on optimal area algorithms for upward drawings of binary trees

paper_content:

Abstract The goal of this paper is to investigate the area requirements for upward grid drawings of binary trees. First, we show that there is a family of binary trees with n vertices that require ω(n log n) area; this bound is tight to within a constant factor, i.e. any binary tree with n vertices can be drawn in O(n log n) area. Then we present an algorithm for constructing an upward drawing of a complete binary tree with n vertices in O(n) area, and, finally, we extend this result to the drawings of Fibonacci trees.
---
paper_title: Optimizing area and aspect ratio in straight-line orthogonal tree drawings

paper_content:

We investigate the problem of drawing an arbitrary n-node binary tree orthogonally and upwardly in an integer grid using straight-line edges. We show that one can simultaneously achieve good area bounds while also allowing the aspect ratio to be chosen as a fixed constant or a parameter under the user's control. In addition, we show that one can also achieve an additional desirable aesthetic criterion, which we call "subtree separation". Our drawings require O(n logn) area, which we show is optimal to within constant factors in the worst case (i.e. there are trees that need Ω(n logn) area for any upward orthogonal straight-line drawing with good aspect ratio). An improvement for non-upward drawings is briefly mentioned.
---
paper_title: Area-efficient order-preserving planar straight-line drawings of ordered trees

paper_content:

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.
---
paper_title: A note on optimal area algorithms for upward drawings of binary trees

paper_content:

Abstract The goal of this paper is to investigate the area requirements for upward grid drawings of binary trees. First, we show that there is a family of binary trees with n vertices that require ω(n log n) area; this bound is tight to within a constant factor, i.e. any binary tree with n vertices can be drawn in O(n log n) area. Then we present an algorithm for constructing an upward drawing of a complete binary tree with n vertices in O(n) area, and, finally, we extend this result to the drawings of Fibonacci trees.
---
paper_title: A near-linear area bound for drawing binary trees

paper_content:

AbstractWe present several simple methods to construct planar, strictly upward, strongly order-preserving, straight-line drawings of any n -node binary tree. In particular, it is shown that O(n1+ɛ) area is always sufficient for an arbitrary constant ɛ>0 .
---
paper_title: Small area drawings of outerplanar graphs

paper_content:

We show three linear time algorithms for constructing planar straight-line grid drawings of outerplanar graphs. The first and the second algorithm are for balanced outerplanar graphs. Both require linear area. The drawings produced by the first algorithm are not outerplanar while those produced by the second algorithm are. On the other hand, the first algorithm constructs drawings with better angular resolution. The third algorithm constructs outerplanar drawings of general outerplanar graphs with O(n1.48) area. Further, we study the interplay between the area requirements of the drawings of an outerplanar graph and the area requirements of a special class of drawings of its dual tree.
---
paper_title: Straight-Line Orthogonal Drawings of Binary and Ternary Trees

paper_content:

In this paper we provide upper and lower bounds on the area requirement of straight-line orthogonal drawings of n-node binary and ternary trees. Namely, we show algorithms for constructing orderpreserving straight-line orthogonal drawings of binary trees in O(n1.5) area, straight-line orthogonal drawings of ternary trees in O(n1.631) area, and straight-line orthogonal drawings of complete ternary trees in O(n1.262) area. As far as we know, the ones we present are the first algorithms achieving sub-quadratic area for these problems. Further, for upward order-preserving straight-line orthogonal drawings of binary trees and for order-preserving straight-line orthogonal drawings of ternary trees we provide Ω(n2) area lower bounds, that we also prove to be tight.
---
paper_title: Area-efficient algorithms for straight-line tree drawings

paper_content:

Abstract We investigate several straight-line drawing problems for bounded-degree trees in the integer grid without edge crossings under various types of drawings: (1) upward drawings whose edges are drawn as vertically monotone chains, a sequence of line segments, from a parent to its children, (2) order-preserving drawings which preserve the left-to-right order of the children of each vertex, and (3) orthogonal straight-line drawings in which each edge is represented as a single vertical or horizontal segment. Main contribution of this paper is a unified framework to reduce the upper bound on area for the straight-line drawing problems from O (n log n) (Crescenzi et al., 1992) to O (n loglog n) . This is the first solution of an open problem stated by Garg et al. (1993). We also show that any binary tree admits a small area drawing satisfying any given aspect ratio in the orthogonal straight-line drawing type. Our results are briefly summarized as follows. Let T be a bounded-degree tree with n vertices. Firstly, we show that T admits an upward straight-line drawing with area O (n loglog n) . If T is binary, we can obtain an O (n loglog n) -area upward orthogonal drawing in which each edge is drawn as a chain of at most two orthogonal segments and which has O (n/ log n) bends in total. Secondly, we present O (n loglog n) -area (respectively, -volume) orthogonal straight-line drawing algorithms for binary trees with arbitrary aspect ratios in 2-dimension (respectively, 3-dimension). Finally, we present some experimental results which shows the area requirements, in practice, for (order-preserving) upward drawing are much smaller than theoretical bounds obtained through analysis.
---
paper_title: Drawing Outer-Planar Graphs in O(n log n) Area

paper_content:

In this paper, we study drawings of outer-planar graphs in various models. We show that O(n log n) area can be achieved for such drawings if edges are allowed to have bends or if vertices may be represented by boxes. The question of straight-line grid-drawings of outer-planar graphs in o(n 2 ) area remains open.
---
paper_title: Optimizing area and aspect ratio in straight-line orthogonal tree drawings

paper_content:

We investigate the problem of drawing an arbitrary n-node binary tree orthogonally and upwardly in an integer grid using straight-line edges. We show that one can simultaneously achieve good area bounds while also allowing the aspect ratio to be chosen as a fixed constant or a parameter under the user's control. In addition, we show that one can also achieve an additional desirable aesthetic criterion, which we call "subtree separation". Our drawings require O(n logn) area, which we show is optimal to within constant factors in the worst case (i.e. there are trees that need Ω(n logn) area for any upward orthogonal straight-line drawing with good aspect ratio). An improvement for non-upward drawings is briefly mentioned.
---
paper_title: Straight-Line Orthogonal Drawings of Binary and Ternary Trees

paper_content:

In this paper we provide upper and lower bounds on the area requirement of straight-line orthogonal drawings of n-node binary and ternary trees. Namely, we show algorithms for constructing orderpreserving straight-line orthogonal drawings of binary trees in O(n1.5) area, straight-line orthogonal drawings of ternary trees in O(n1.631) area, and straight-line orthogonal drawings of complete ternary trees in O(n1.262) area. As far as we know, the ones we present are the first algorithms achieving sub-quadratic area for these problems. Further, for upward order-preserving straight-line orthogonal drawings of binary trees and for order-preserving straight-line orthogonal drawings of ternary trees we provide Ω(n2) area lower bounds, that we also prove to be tight.
---
paper_title: A note on optimal area algorithms for upward drawings of binary trees

paper_content:

Abstract The goal of this paper is to investigate the area requirements for upward grid drawings of binary trees. First, we show that there is a family of binary trees with n vertices that require ω(n log n) area; this bound is tight to within a constant factor, i.e. any binary tree with n vertices can be drawn in O(n log n) area. Then we present an algorithm for constructing an upward drawing of a complete binary tree with n vertices in O(n) area, and, finally, we extend this result to the drawings of Fibonacci trees.
---
paper_title: Optimizing area and aspect ratio in straight-line orthogonal tree drawings

paper_content:

We investigate the problem of drawing an arbitrary n-node binary tree orthogonally and upwardly in an integer grid using straight-line edges. We show that one can simultaneously achieve good area bounds while also allowing the aspect ratio to be chosen as a fixed constant or a parameter under the user's control. In addition, we show that one can also achieve an additional desirable aesthetic criterion, which we call "subtree separation". Our drawings require O(n logn) area, which we show is optimal to within constant factors in the worst case (i.e. there are trees that need Ω(n logn) area for any upward orthogonal straight-line drawing with good aspect ratio). An improvement for non-upward drawings is briefly mentioned.
---
paper_title: Small Drawings of Outerplanar Graphs, Series-Parallel Graphs, and Other Planar Graphs

paper_content:

In this paper, we study small planar drawings of planar graphs. For arbitrary planar graphs, Θ(n 2) is the established upper and lower bound on the worst-case area. A long-standing open problem is to determine for what graphs a smaller area can be achieved. We show here that series-parallel graphs can be drawn in O(n 3/2) area, and outerplanar graphs can be drawn in O(nlog n) area, but 2-outerplanar graphs and planar graphs of proper pathwidth 3 require Ω(n 2) area. Our drawings are visibility representations, which can be converted to polyline drawings of asymptotically the same area.
---
paper_title: A note on optimal area algorithms for upward drawings of binary trees

paper_content:

Abstract The goal of this paper is to investigate the area requirements for upward grid drawings of binary trees. First, we show that there is a family of binary trees with n vertices that require ω(n log n) area; this bound is tight to within a constant factor, i.e. any binary tree with n vertices can be drawn in O(n log n) area. Then we present an algorithm for constructing an upward drawing of a complete binary tree with n vertices in O(n) area, and, finally, we extend this result to the drawings of Fibonacci trees.
---
paper_title: Planar Upward Tree Drawings with Optimal Area

paper_content:

Rooted trees are usually drawn planar and upward, i.e., without crossings and with-out any parent placed below its child. In this paper we investigate the area requirement of planar upward drawings of rooted trees. We give tight upper and lower bounds on the area of various types of drawings, and provide linear-time algorithms for constructing optimal area drawings. Let T be a bounded-degree rooted tree with N nodes. Our results are summarized as follows: • We show that T admits a planar polyline upward grid drawing with area O(N), and with width O(Nα) for any prespecified constant a such that 0<α<1. • If T is a binary tree, we show that T admits a planar orthogonal upward grid drawing with area O (N log log N). • We show that if T is ordered, it admits an O(N log N)-area planar upward grid drawing that preserves the left-to-right ordering of the children of each node. • We show that all of the above area bounds are asymptotically optimal in the worst case. • We present O(N)-time algorithms for constructing each of the above types of drawings of T with asymptotically optimal area. • We report on the experimentation of our algorithm for constructing planar polyline upward grid drawings, performed on trees with up to 24 million nodes.
---
paper_title: Universality considerations in VLSI circuits

paper_content:

The problem of embedding the interconnection pattern of a circuit into a two-dimensional surface of minimal area is discussed. Since even for some natural patterns graphs containing m connections may require Ω(m2) area, in order to achieve compact embeddings restricted classes of graphs have to be considered. For example, arbitrary trees (of bounded degree) can be embedded in linear area without edges crossing over. Planar graphs can be embedded efficiently only if crossovers are allowed in the embedding.
---
paper_title: A note on optimal area algorithms for upward drawings of binary trees

paper_content:

Abstract The goal of this paper is to investigate the area requirements for upward grid drawings of binary trees. First, we show that there is a family of binary trees with n vertices that require ω(n log n) area; this bound is tight to within a constant factor, i.e. any binary tree with n vertices can be drawn in O(n log n) area. Then we present an algorithm for constructing an upward drawing of a complete binary tree with n vertices in O(n) area, and, finally, we extend this result to the drawings of Fibonacci trees.
---
paper_title: Planar Upward Tree Drawings with Optimal Area

paper_content:

Rooted trees are usually drawn planar and upward, i.e., without crossings and with-out any parent placed below its child. In this paper we investigate the area requirement of planar upward drawings of rooted trees. We give tight upper and lower bounds on the area of various types of drawings, and provide linear-time algorithms for constructing optimal area drawings. Let T be a bounded-degree rooted tree with N nodes. Our results are summarized as follows: • We show that T admits a planar polyline upward grid drawing with area O(N), and with width O(Nα) for any prespecified constant a such that 0<α<1. • If T is a binary tree, we show that T admits a planar orthogonal upward grid drawing with area O (N log log N). • We show that if T is ordered, it admits an O(N log N)-area planar upward grid drawing that preserves the left-to-right ordering of the children of each node. • We show that all of the above area bounds are asymptotically optimal in the worst case. • We present O(N)-time algorithms for constructing each of the above types of drawings of T with asymptotically optimal area. • We report on the experimentation of our algorithm for constructing planar polyline upward grid drawings, performed on trees with up to 24 million nodes.
---
paper_title: On linear area embedding of planar graphs

paper_content:

Planar embedding with minimal area of graphs on an integer grid is one of the major issues in VLSI. Valiant [1981] gave an algorithm to construct a planar embedding for trees in linear area; he also proved that there are planar graphs that require quadratic area. We give an algorithm to embed outerplanar graphs in linear area. We extend this algorithm to work for every planar graph that has the following property: for every vertex there exists a path of length less than K to the exterior face, where K is a constant. Finally, finding a minimal embedding area is shown to be NP-complete for forests, and hence for more general types of graphs.
---
paper_title: On the Compuational Complexity of Upward and Rectilinear Planarity Testing

paper_content:

A directed graph is upward planar if it can be drawn in the plane such that every edge is a monotonically increasing curve in the vertical direction, and no two edges cross. An undirected graph is rectilinear planar if it can be drawn in the plane such that every edge is a horizontal or vertical segment, and no two edges cross. Testing upward planarity and rectilinear planarity are fundamental problems in the effective visualization of various graph and network structures. In this paper we show that upward planarity testing and rectilinear planarity testing are NP-complete problems. We also show that it is NP-hard to approximate the minimum number of bends in a planar orthogonal drawing of an n-vertex graph with an O(n1−∈) error, for any ∈>0.
---
paper_title: Algorithms for Plane Representations of Acyclic Digraphs

paper_content:

Abstract Acyclic digraphs are widely used for representing hierarchical structures. Examples include PERT networks, subroutine-call graphs, family trees, organization charts, Hasse diagrams, and ISA hierarchies in knowledge representation diagrams. We investigate the problem of representing acyclic digraphs in the plane in such a way that all edges flow in the same direction, e.g., from the left to the right or from the bottom to the top. Three plane representations are considered: straight drawings , visibility representations , and grid drawings . We provide efficient algorithms that construct these representations with all edges flowing in the same direction. The time complexity is O( n ) for visibility representations and grid drawings, and O( n log n ) for straight drawings, where n is the number of vertices of the digraph. For covering digraphs of lattices, the complexity of constructing straight drawings is O( n ). We also show that the planar digraphs that admit any one of these representations are exactly the subgraphs of planar st-graphs .
---
paper_title: On minimum area planar upward drawings of directed trees and other families of directed acyclic graphs

paper_content:

It has been shown in [9] that there exist planar digraphs that require exponential area in every upward straight-line planar drawing. On the other hand, upward poly-line planar drawings of planar graphs can be realized in Θ(n2) area [9]. In this paper we consider families of DAGs that naturally arise in practice, like DAGs whose underlying graph is a tree (directed trees), is a bipartite graph (directed bipartite graphs), or is an outerplanar graph (directed outerplanar graphs). Concerning directed trees, we show that optimal Θ(n log n) area upward straight-line/polyline planar drawings can be constructed. However, we prove that if the order of the neighbors of each node is assigned, then exponential area is required for straight-line upward drawings and quadratic area is required for poly-line upward drawings, results surprisingly and sharply contrasting with the area bounds for planar upward drawings of undirected trees. After having established tight bounds on the area requirements of planar upward drawings of several families of directed trees, we show how the results obtained for trees can be exploited to determine asymptotic optimal values for the area occupation of planar upward drawings of directed bipartite graphs and directed outerplanar graphs.
---
paper_title: Area Requirement and Symmetry Display of Planar Upward Drawings

paper_content:

In this paper we investigate the problem of constructing planar straight-line drawings of acyclic digraphs such that all the edges flow in the same direction, e.g., from bottom to top. Our contribution is twofold. First we show the existence of a family of planar acyclic digraphs that require exponential area for any such drawing. Second, motivated by the preceding lower bound, we relax the straight-line constraint and allow bends along the edges. We present a linear-time algorithm that produces drawings of planarst-graphs with a small number of bends, asymptotically optimal area, and such that symmetries and isomorphisms of the digraph are displayed. If the digraph has no transitive edges, then the drawing obtained has no bends. Also, a variation of the algorithm produces drawings with exact minimum area.
---
paper_title: Upward drawings of triconnected digraphs

paper_content:

A polynomial-time algorithm for testing if a triconnected directed graph has an upward drkwing is presented. An upward drkwing is a planar drkwing such that all the edges flow in a common direction (e.g., from bottom to top). The problem arises in the fields of automatic graph drkwing and ordered sets, and has been open for several years. The proposed algorithm is based on a new combinatorial characterization that maps the problem into a max-flow problem on a sparse network; the time complexity isO(n+r 2) , wheren is the number of vertices andr is the number of sources and sinks of the directed graph. If the directed graph has an upward drkwing, the algorithm allows us to construct one easily.
---
paper_title: On minimum area planar upward drawings of directed trees and other families of directed acyclic graphs

paper_content:

It has been shown in [9] that there exist planar digraphs that require exponential area in every upward straight-line planar drawing. On the other hand, upward poly-line planar drawings of planar graphs can be realized in Θ(n2) area [9]. In this paper we consider families of DAGs that naturally arise in practice, like DAGs whose underlying graph is a tree (directed trees), is a bipartite graph (directed bipartite graphs), or is an outerplanar graph (directed outerplanar graphs). Concerning directed trees, we show that optimal Θ(n log n) area upward straight-line/polyline planar drawings can be constructed. However, we prove that if the order of the neighbors of each node is assigned, then exponential area is required for straight-line upward drawings and quadratic area is required for poly-line upward drawings, results surprisingly and sharply contrasting with the area bounds for planar upward drawings of undirected trees. After having established tight bounds on the area requirements of planar upward drawings of several families of directed trees, we show how the results obtained for trees can be exploited to determine asymptotic optimal values for the area occupation of planar upward drawings of directed bipartite graphs and directed outerplanar graphs.
---
paper_title: Upward spirality and upward planarity testing

paper_content:

The upward planarity testing problem is known to be NP-hard. We describe an O(n 4 )-time upward planarity testing and embedding algorithm for the class of digraphs that do not contain rigid triconnected components. We also present a new FPT algorithm that solves the upward planarity testing and embedding problem for general digraphs.
---
paper_title: Algorithms for Plane Representations of Acyclic Digraphs

paper_content:

Abstract Acyclic digraphs are widely used for representing hierarchical structures. Examples include PERT networks, subroutine-call graphs, family trees, organization charts, Hasse diagrams, and ISA hierarchies in knowledge representation diagrams. We investigate the problem of representing acyclic digraphs in the plane in such a way that all edges flow in the same direction, e.g., from the left to the right or from the bottom to the top. Three plane representations are considered: straight drawings , visibility representations , and grid drawings . We provide efficient algorithms that construct these representations with all edges flowing in the same direction. The time complexity is O( n ) for visibility representations and grid drawings, and O( n log n ) for straight drawings, where n is the number of vertices of the digraph. For covering digraphs of lattices, the complexity of constructing straight drawings is O( n ). We also show that the planar digraphs that admit any one of these representations are exactly the subgraphs of planar st-graphs .
---
paper_title: On Succinctness of Geometric Greedy Routing in Euclidean Plane

paper_content:

Geometric greedy routing uses (virtual) geographic point locations as addresses for the purposes of routing, while routing decisions are made by each node individually based only on local information. It requires that the network topology is greedily embedded in a metric space through assigning virtual coordinates to the nodes in the network. Recent research pointed out that such scheme is significantly more efficient than other traditional routing schemes only if the virtual coordinates are succinctly represented (i.e., using $O(poly(\log n))$ bits per coordinate) in the greedy embedding, an issue that has been overlooked for a long time. In this paper we prove that such succinctness is not achievable in Euclidean plane, assuming that Cartesian or polar coordinate system is used, the network topology is a planar graph, and the planar embedding is preserved during the process of greedy embedding. Indeed, we provide a counter example to show that in this situation, some coordinates must take $\Omega(n)$ bits to represent.
---
paper_title: On Succinct Greedy Drawings of Plane Triangulations and 3-Connected Plane Graphs

paper_content:

Geometric routing by using virtual locations is an elegant way for solving network routing problems. In its simplest form, greedy routing, a message is simply forwarded to a neighbor that is closer to the destination. It has been an open conjecture whether every 3-connected plane graph has a greedy drawing in the Euclidean plane R 2 (by Papadimitriou and Ratajczak in Theor. Comp. Sci. 344(1):3–14, 2005). Leighton and Moitra (Discrete Comput. Geom. 44(3):686–705, 2010) recently settled this conjecture positively. One main drawback of this approach is that the coordinates of the virtual locations require Ω(nlogn) bits to represent (the same space usage as traditional routing table approaches). This makes greedy routing infeasible in applications.
---
paper_title: C-Planarity of C-Connected Clustered Graphs

paper_content:

We present the first characterization of c-planarity for c-connected clustered graphs. The characterization is based on the interplay between the hierarchy of the clusters and the hierarchies of the triconnected and biconnected components of the underlying graph. Based on such a characterization, we provide a linear-time c-planarity testing and embedding algorithm for c-connected clustered graphs. The algorithm is reasonably easy to implement, since it exploits as building blocks simple algorithmic tools like the computation of lowest common ancestors, minimum and maximum spanning trees, and counting sorts. It also makes use of well-known data structures as SPQR-trees and BC-trees. If the test fails, the algorithm identifies a structural element responsible for the non-cplanarity of the input clustered graph.
---
paper_title: Clustered Planarity: Clusters with Few Outgoing Edges

paper_content:

We present a linear algorithm for c-planarity testing of clustered graphs, in which every cluster has at most four outgoing edges.
---
paper_title: Efficient C-Planarity Testing for Embedded Flat Clustered Graphs with Small Faces

paper_content:

The disclosure is directed to a system for storing and reproducing analog or digital information, such as television information. There is provided a recording disk having a mechanical guiding track formed in a spiral or circular pattern on a surface thereof. A signal recovery device is provided and includes mechanical tracking means to effect guiding along the mechanical guiding track of the disk. The signal recovery subsystem also includes an optical scanning means for scanning the optical records. In the preferred embodiment of the invention, the signal recovery device includes mechanical driving means, synchronized with the optical scanning means, for engaging the guiding track and causing motion of the disk with respect to the signal recovery device. The disk is preferably mounted on a passive turntable, and rotation of the disk and turntable is achieved by the mechanical driving means of the signal recovery device acting directly on the disk. Since the mechanical driving means is synchronized with the optical scanning means, proper tracking is achieved, and this is done without the need for complicated servomechanisms as would be needed for precise independent direct driving of the turntable. In an embodiment of the invention, the mechanical guiding track has serrations thereon and the mechanical driving means in the signal recovery device includes a rotatable member which engages the serrations to effect motion of the recording disk.
---
paper_title: Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs

paper_content:

Hierarchical graphs and clustered graphs are useful non-classical graph models for structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both have applications in CASE tools, software visualization and VLSI design. Drawing algorithms for hierarchical graphs have been well investigated. However, the problem of planar straight-line representation has not been solved completely. In this paper we answer the question: does every planar hierarchical graph admit a planar straight-line hierarchical drawing? We present an algorithm that constructs such drawings in linear time. Also, we answer a basic question for clustered graphs, that is, does every planar clustered graph admit a planar straight-line drawing with clusters drawn as convex polygons? We provide a method for such drawings based on our algorithm for hierarchical graphs.
---
paper_title: Splitting Clusters to Get C-Planarity

paper_content:

In this paper we introduce a generalization of the c-planarity testing problem for clustered graphs. Namely, given a clustered graph, the goal of the Split-C-Planarity problem is to split as few clusters as possible in order to make the graph c-planar. Determining whether zero splits are enough coincides with testing c-planarity. We show that Split-C-Planarity is NP-complete for c-connected clustered triangulations and for non-c-connected clustered paths and cycles. On the other hand, we present a polynomial-time algorithm for flat c-connected clustered graphs whose underlying graph is a biconnected series-parallel graph, both in the fixed and in the variable embedding setting, when the splits are assumed to maintain the c-connectivity of the clusters.
---
paper_title: Completely connected clustered graphs

paper_content:

Planar drawings of clustered graphs are considered. We introduce the notion of completely connected clustered graphs, i.e. hierarchically clustered graphs that have the property that not only every cluster but also each complement of a cluster induces a connected subgraph. As a main result, we prove that a completely connected clustered graph is c-planar if and only if the underlying graph is planar. Further, we investigate the influence of the root of the inclusion tree to the choice of the outer face of the underlying graph and vice versa.
---
paper_title: A Linear Time Algorithm to Recognize Clustered Graphs and Its Parallelization

paper_content:

We develop a linear time algorithm for the following problem: Given a graph G and a hierarchical clustering of the vertices such that all clusters induce connected subgraphs, determine whether G may be embedded into the plane such that no cluster has a hole.
---
paper_title: On Embedding a Cycle in a Plane Graph

paper_content:

Consider a planar drawing ${\it \Gamma}$of a planar graph G such that the vertices are drawn as small circles and the edges are drawn as thin strips. Consider a cycle c of G. Is it possible to draw c as a non-intersecting closed curve inside ${\it \Gamma}$, following the circles that correspond in ${\it \Gamma}$to the vertices of c and the strips that connect them? We show that this test can be done in polynomial time and study this problem in the framework of clustered planarity for highly non-connected clustered graphs.
---
paper_title: How to draw a clustered tree

paper_content:

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 asymptotic optimal area.
---
paper_title: Clustered Planarity: Small Clusters in Cycles and Eulerian Graphs

paper_content:

We present several polynomial-time algorithms for c-planarity testing for cluster hierarchy C containing clusters of size at most three. The main result is an O(|C| + n)-time algorithm for clusters of size at most three on a cycle. The result is then generalized to a special class of Eulerian graphs, namely graphs obtained from a 3-connected planar graph of fixed size k by multiplying and then subdividing edges. An O(3 · k · n)-time algorithm is presented. We further give an O(|C| + n)-time algorithm for general 3-connected planar graphs. Submitted: December 2007 Reviewed: November 2008 Revised: February 2009 Accepted: August 2009 Final: September 2009 Published: November 2009 Article type: Regular paper Communicated by: S.-H. Hong and T. Nishizeki An extended abstract of this paper appeared in proceedings of Graph Drawing 2007. [14] Department of Applied Mathematics is supported by project 1M0021620838 of the Czech Ministry of Education. Institute for Theoretical Computer Science is supported by grant 1M0545 of the Czech Ministry of Education. The 4th author was supported by the grant GAUK 154907. The 5th author and the 6th author were supported by grant 201/05/H014 of the Czech Science Foundation. The 5th author was also partially supported by the ERASMUS program and by the DFG, project NI 369/4 (PIAF), while visiting Friedrich-Schiller-Universitat Jena, Germany (October 2008–
---
paper_title: Clustered Planarity: Embedded Clustered Graphs with Two-Component Clusters

paper_content:

We present a polynomial-time algorithm for c-planarity test- ing of clustered graphs with fixed plane embedding and such that every cluster induces a subgraph with at most two connected components.
---
paper_title: Area Requirement and Symmetry Display of Planar Upward Drawings

paper_content:

In this paper we investigate the problem of constructing planar straight-line drawings of acyclic digraphs such that all the edges flow in the same direction, e.g., from bottom to top. Our contribution is twofold. First we show the existence of a family of planar acyclic digraphs that require exponential area for any such drawing. Second, motivated by the preceding lower bound, we relax the straight-line constraint and allow bends along the edges. We present a linear-time algorithm that produces drawings of planarst-graphs with a small number of bends, asymptotically optimal area, and such that symmetries and isomorphisms of the digraph are displayed. If the digraph has no transitive edges, then the drawing obtained has no bends. Also, a variation of the algorithm produces drawings with exact minimum area.
---
paper_title: Planarity for Clustered Graphs

paper_content:

In this paper, we introduce a new graph model known as clustered graphs, i.e. graphs with recursive clustering structures. This graph model has many applications in informational and mathematical sciences. In particular, we study C-planarity of clustered graphs. Given a clustered graph, the C-planarity testing problem is to determine whether the clustered graph can be drawn without edge crossings, or edge-region crossings. In this paper, we present efficient algorithms for testing C-planarity and finding C-planar embeddings of clustered graphs.
---
paper_title: How to Draw a Planar Clustered Graph

paper_content:

In this paper, we introduce and show how to draw a practical graph structure known as clustered graphs. We present an algorithm which produces planar, straight-line, convex drawings of clustered graphs in O(n2.5) time. We also demonstrate an area lower bound and an angle upper bound for straight-line convex drawings of C-planar graphs. We show that such drawings require Ω(2n) area and the smallest angle is O(1/n). Our bounds are unlike the area and angle bounds of classical graph drawing conventions in which area bound is Ω(n2) and angle bounds are functions of the maximum degree of the graph. Our results indicate important tradeoff between line straightness and area, and between region convexity and area.
---
paper_title: Straight-Line Rectangular Drawings of Clustered Graphs

paper_content:

We show that every c -planar clustered graph admits a straight-line c -planar drawing in which each cluster is represented by an axis-parallel rectangle, thus solving a problem posed by Eades, Feng, Lin, and Nagamochi [Algorithmica, 2006 ].
---

Title: A Survey on Small-Area Planar Graph Drawing

Section 1: Preliminaries
Description 1: Summarize the fundamental concepts and definitions relevant to graph drawing.

Section 2: Planar Drawings, Planar Embeddings, and Planar Graphs
Description 2: Explain the characteristics of planar drawings, planar embeddings, and planar graphs.

Section 3: Maximality and Connectivity
Description 3: Describe the notions of maximal graphs and different levels of connectivity in graphs.

Section 4: Classes of Planar Graphs
Description 4: Discuss various classes of planar graphs, including trees, outerplanar graphs, and series-parallel graphs.

Section 5: Drawing Standards
Description 5: Outline different standards for graph drawings, such as straight-line, poly-line, orthogonal, and visibility representations.

Section 6: Area of a Drawing
Description 6: Explain the significance and calculation of the area of a graph drawing.

Section 7: Directed Graphs and Planar Upward Drawings
Description 7: Discuss directed acyclic graphs (DAGs) and the specifics of upward planar drawings.

Section 8: Proximity Drawings
Description 8: Describe proximity drawings, including Delaunay, Gabriel, relative neighborhood, and nearest neighbor graphs.

Section 9: Clustered Graphs and c-Planar Drawings
Description 9: Detail the structure and drawing conventions for clustered graphs and c-planar drawings.

Section 10: Straight-line Drawings
Description 10: Explore algorithms and bounds for straight-line drawings of planar graphs.

Section 11: 4-Connected and Bipartite Planar Graphs
Description 11: Provide algorithms and bounds for drawing 4-connected and bipartite planar graphs.

Section 12: Series-Parallel Graphs
Description 12: Discuss area requirements and algorithms for series-parallel graphs.

Section 13: Outerplanar Graphs
Description 13: Examine drawing algorithms and area bounds for outerplanar graphs.

Section 14: Trees
Description 14: Present algorithms and bounds for drawing various types of trees.

Section 15: Poly-line Drawings
Description 15: Summarize the methods for constructing poly-line drawings of planar graphs and their subclasses.

Section 16: Upward Drawings
Description 16: Discuss area bounds and algorithms for upward drawings of planar DAGs.

Section 17: Convex Drawings
Description 17: Review algorithms for constructing small-area convex and strictly-convex drawings.

Section 18: Clustered Graph Drawings
Description 18: Provide details on c-planar drawings and algorithms for clustered graphs.