Area (graph drawing)

Last updated

In graph drawing, the area used by a drawing is a commonly used way of measuring its quality.

Contents

Definition

For a drawing style in which the vertices are placed on the integer lattice, the area of the drawing may be defined as the area of the smallest axis-aligned bounding box of the drawing: that is, it the product of the largest difference in x-coordinates of two vertices with the largest difference in y-coordinates. For other drawing styles, in which vertices are placed more freely, the drawing may be scaled so that the closest pair of vertices have distance one from each other, after which the area can again be defined as the area of a smallest bounding box of a drawing. Alternatively, the area can be defined as the area of the convex hull of the drawing, again after appropriate scaling. [1]

Polynomial bounds

For straight-line drawings of planar graphs with n vertices, the optimal worst-case bound on the area of a drawing is Θ(n2). The nested triangles graph requires this much area no matter how it is embedded, [2] and several methods are known that can draw planar graphs with at most quadratic area. [3] [4] Binary trees, and trees of bounded degree more generally, have drawings with linear or near-linear area, depending on the drawing style. [5] [6] [7] [8] [9] Every outerplanar graph has a straight-line outerplanar drawing with area subquadratic in its number of vertices, [10] [11] If bends or crossings are allowed, then outerplanar graphs have drawings with near-linear area. [12] [13] However, drawing series–parallel graphs requires an area larger than n multiplied by a superpolylogarithmic factor, even if edges can be drawn as polylines. [14]

Exponential bounds

In contrast to these polynomial bounds, some drawing styles may exhibit exponential growth in their areas, implying that these styles may be suitable only for small graphs. An example is upward planar drawing of planar directed acyclic graphs, where the area of an n-vertex drawing may be proportional to 2n in the worst case. [15] Even plane trees may require exponential area, if they are to be drawn with straight edges that preserve a fixed cyclic order around each vertex and must be equally spaced around the vertex. [16]

Related Research Articles

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

<span class="mw-page-title-main">Graph drawing</span> Visualization of node-link graphs

Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, linguistics, and bioinformatics.

<span class="mw-page-title-main">Hasse diagram</span> Visual depiction of a partially ordered set

In order theory, a Hasse diagram is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction. Concretely, for a partially ordered set one represents each element of as a vertex in the plane and draws a line segment or curve that goes upward from one vertex to another vertex whenever and covers . These curves may cross each other but must not touch any vertices other than their endpoints. Such a diagram, with labeled vertices, uniquely determines its partial order.

<span class="mw-page-title-main">Outerplanar graph</span> Non-crossing graph with vertices on outer face

In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

<span class="mw-page-title-main">Polygon triangulation</span> Partition of a simple polygon into triangles

In computational geometry, polygon triangulation is the partition of a polygonal area P into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is P.

<span class="mw-page-title-main">Book embedding</span> Graph layout on multiple half-planes

In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into a book, a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the spine, and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number.

In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number.

In graph theory, the planarity testing problem is the algorithmic problem of testing whether a given graph is a planar graph. This is a well-studied problem in computer science for which many practical algorithms have emerged, many taking advantage of novel data structures. Most of these methods operate in O(n) time, where n is the number of edges in the graph, which is asymptotically optimal. Rather than just being a single Boolean value, the output of a planarity testing algorithm may be a planar graph embedding, if the graph is planar, or an obstacle to planarity such as a Kuratowski subgraph if it is not.

<span class="mw-page-title-main">Halin graph</span> Mathematical tree with cycle through leaves

In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross, and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.

In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.

<span class="mw-page-title-main">Angular resolution (graph drawing)</span> Sharpest angle between edges at a vertex

In graph drawing, the angular resolution of a drawing of a graph is the sharpest angle formed by any two edges that meet at a common vertex of the drawing.

<span class="mw-page-title-main">Slope number</span> Number of edge slopes in graph drawing

In graph drawing and geometric graph theory, the slope number of a graph is the minimum possible number of distinct slopes of edges in a drawing of the graph in which vertices are represented as points in the Euclidean plane and edges are represented as line segments that do not pass through any non-incident vertex.

<span class="mw-page-title-main">1-planar graph</span>

In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge. If a 1-planar graph, one of the most natural generalizations of planar graphs, is drawn that way, the drawing is called a 1-plane graph or 1-planar embedding of the graph.

In graph drawing, a universal point set of order n is a set S of points in the Euclidean plane with the property that every n-vertex planar graph has a straight-line drawing in which the vertices are all placed at points of S.

In graph theory, a bipolar orientation or st-orientation of an undirected graph is an assignment of a direction to each edge that causes the graph to become a directed acyclic graph with a single source s and a single sink t, and an st-numbering of the graph is a topological ordering of the resulting directed acyclic graph.

<span class="mw-page-title-main">Upward planar drawing</span> Graph with edges non-crossing and upward

In graph drawing, an upward planar drawing of a directed acyclic graph is an embedding of the graph into the Euclidean plane, in which the edges are represented as non-crossing monotonic upwards curves. That is, the curve representing each edge should have the property that every horizontal line intersects it in at most one point, and no two edges may intersect except at a shared endpoint. In this sense, it is the ideal case for layered graph drawing, a style of graph drawing in which edges are monotonic curves that may cross, but in which crossings are to be minimized.

<span class="mw-page-title-main">Dominance drawing</span> Graph where coordinates show reachability

Dominance drawing is a style of graph drawing of directed acyclic graphs that makes the reachability relations between vertices visually apparent. In dominance drawing, vertices are placed at distinct points of the Euclidean plane and a vertex v is reachable from another vertex u if and only if both Cartesian coordinates of v are greater than or equal to the coordinates of u. The edges of a dominance drawing may be drawn either as straight line segments, or, in some cases, as polygonal chains.

In the mathematical field of graph theory, planarization is a method of extending graph drawing methods from planar graphs to graphs that are not planar, by embedding the non-planar graphs within a larger planar graph.

In graph drawing styles that represent the edges of a graph by polylines, it is desirable to minimize the number of bends per edge or the total number of bends in a drawing. Bend minimization is the algorithmic problem of finding a drawing that minimizes these quantities.

Simultaneous embedding is a technique in graph drawing and information visualization for visualizing two or more different graphs on the same or overlapping sets of labeled vertices, while avoiding crossings within both graphs. Crossings between an edge of one graph and an edge of the other graph are allowed.

References

  1. ↑ Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), Graph Drawing: Algorithms for the Visualization of Graphs (1st ed.), Prentice Hall, pp. 14–15, ISBN   0133016153 .
  2. ↑ Dolev, Danny; Leighton, Tom; Trickey, Howard (1984), "Planar embedding of planar graphs" (PDF), Advances in Computing Research, 2: 147–161
  3. ↑ de Fraysseix, Hubert; Pach, János; Pollack, Richard (1988), "Small sets supporting Fary embeddings of planar graphs", Twentieth Annual ACM Symposium on Theory of Computing , pp. 426–433, doi: 10.1145/62212.62254 , ISBN   0-89791-264-0, S2CID   15230919 .
  4. ↑ Schnyder, Walter (1990), "Embedding planar graphs on the grid", Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA), pp. 138–148.
  5. ↑ Crescenzi, P.; Di Battista, G.; Piperno, A. (1992), "A note on optimal area algorithms for upward drawings of binary trees", Computational Geometry Theory & Applications, 2 (4): 187–200, doi: 10.1016/0925-7721(92)90021-J , MR   1196545 .
  6. ↑ Garg, Ashim; Goodrich, Michael T.; Tamassia, Roberto (1996), "Planar upward tree drawings with optimal area", International Journal of Computational Geometry & Applications, 6 (3): 333–356, doi:10.1142/S0218195996000228, MR   1409650 .
  7. ↑ Chan, T. M. (2002), "A near-linear area bound for drawing binary trees", Algorithmica, 34 (1): 1–13, doi:10.1007/s00453-002-0937-x, MR   1912924, S2CID   5122671 .
  8. ↑ Chan, Timothy M.; Goodrich, Michael T.; Kosaraju, S. Rao; Tamassia, Roberto (2002), "Optimizing area and aspect ratio in straight-line orthogonal tree drawings", Computational Geometry Theory & Applications, 23 (2): 153–162, doi: 10.1016/S0925-7721(01)00066-9 , MR   1922928 .
  9. ↑ Garg, Ashim; Rusu, Adrian (2004), "Straight-line drawings of binary trees with linear area and arbitrary aspect ratio", Journal of Graph Algorithms and Applications , 8 (2): 135–160, doi: 10.7155/jgaa.00086 , MR   2164808 .
  10. ↑ Garg, Ashim; Rusu, Adrian (2007), "Area-efficient planar straight-line drawings of outerplanar graphs", Discrete Applied Mathematics, 155 (9): 1116–1140, doi: 10.1016/j.dam.2005.12.008 , MR   2321019 .
  11. ↑ Di Battista, Giuseppe; Frati, Fabrizio (2009), "Small area drawings of outerplanar graphs", Algorithmica, 54 (1): 25–53, doi:10.1007/s00453-007-9117-3, MR   2496664, S2CID   2814656 .
  12. ↑ Biedl, Therese (2002), "Drawing outer-planar graphs in O(n log n) area", Graph Drawing:10th International Symposium, GD 2002, Irvine, CA, USA, August 26–28, 2002, Revised Papers, Lecture Notes in Computer Science, vol. 2528, Springer, pp. 54–65, doi: 10.1007/3-540-36151-0_6 , MR   2063411 .
  13. ↑ Di Giacomo, Emilio; Didimo, Walter; Liotta, Giuseppe; Montecchiani, Fabrizio (2013), "Area requirement of graph drawings with few crossings per edge", Computational Geometry Theory & Applications, 46 (8): 909–916, doi: 10.1016/j.comgeo.2013.03.001 , MR   3061453 .
  14. ↑ Frati, Fabrizio (2011), "Improved lower bounds on the area requirements of series–parallel graphs", Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21–24, 2010, Revised Selected Papers, Lecture Notes in Computer Science, vol. 6502, pp. 220–225, doi: 10.1007/978-3-642-18469-7_20 , MR   2781267 .
  15. ↑ Di Battista, Giuseppe; Tamassia, Roberto; Tollis, Ioannis G. (1992), "Area requirement and symmetry display of planar upward drawings", Discrete and Computational Geometry , 7 (4): 381–401, doi: 10.1007/BF02187850 , MR   1148953 .
  16. ↑ Duncan, Christian A.; Eppstein, David; Goodrich, Michael T.; Kobourov, Stephen G.; Nöllenburg, Martin (2013), "Drawing trees with perfect angular resolution and polynomial area", Discrete and Computational Geometry , 49 (2): 157–182, arXiv: 1009.0581 , doi:10.1007/s00454-012-9472-y, MR   3017904, S2CID   5000871 .
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.