Simultaneous embedding

Last updated

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. [1]

Contents

If edges are allowed to be drawn as polylines or curves, then any planar graph may be drawn without crossing with its vertices in arbitrary positions in the plane, where the same vertex placement provides a simultaneous embedding. [1]

There are two restricted models: simultaneous geometric embedding, where each graph must be drawn planarly with line segments representing its edges rather than more complex curves, restricting the two given graphs to subclasses of the planar graphs, and simultaneous embedding with fixed edges, where curves or bends are allowed in the edges, but any edge in both graphs must be represented by the same curve in both drawings. [1] In the unrestricted model, any two planar graphs can have a simultaneous embedding.

Definition

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; it is only crossings between two edges of the same graph that are disallowed. [1]

If edges are allowed to be drawn as polylines or curves, then any planar graph may be drawn without crossings with its vertices in arbitrary positions in the plane. Using the same vertex placement for two graphs provides a simultaneous embedding of the two graphs. Research has concentrated on finding drawings with few bends, or with few crossings between edges from the two graphs. [1]

There are two restricted models: simultaneous geometric embedding and simultaneous embedding with fixed edges, where curves or bends are allowed in the edges, but any edge present in both graphs must be represented by the same curve in both drawings. When a simultaneous geometric embedding exists, it automatically is also a simultaneous embedding with fixed edges. [1]

For simultaneous embedding problems on more than two graphs, it is standard to assume that all pairs of input graphs have the same intersection as each other; that is, the edge and vertex sets of the graphs form a sunflower. This constraint is known as sunflower intersection. [1]

Simultaneous embedding is closely related to thickness, the minimum number of planar subgraphs that can cover all of the edges of a given graph, and geometric thickness, the minimum number of edge colors needed in a straight-line drawing of a given graph with no crossing between same-colored edges. In particular, the thickness of a given graph is two, if the graph's edges can be partitioned into two subgraphs that have a simultaneous embedding, and the geometric thickness is two, if the edges can be partitioned into two subgraphs with simultaneous geometric embedding. [2]

Geometric

In simultaneous geometric embedding each graph must be drawn as a planar graph with line segments representing its edges rather than more complex curves, restricting the two given graphs to subclasses of the planar graphs. Many results on simultaneous geometric embedding are based on the idea that the Cartesian coordinates of the two given graphs' vertices can be derived from properties of the two graphs. One of the most basic results of this type is the fact that any two path graphs on the same vertex set always have a simultaneous embedding. To find such an embedding, one can use the position of a vertex in the first path as its x-coordinate, and the position of the same vertex in the second path as its y-coordinate. In this way, the first path will be drawn as an x-monotone polyline, a type of curve that is automatically non-self-crossing, and the second path will similarly be drawn as a y-monotone polyline. [3]

This type of drawing places the vertices in an integer lattice of dimensions linear in the graph sizes. Similarly defined layouts also work, with larger but still linear grid sizes, when both graphs are caterpillars or when both are cycle graphs. A simultaneous embedding in a grid of linear dimensions is also possible for any number of graphs that are all stars. Other pairs of graph types that always admit a simultaneous embedding, but that might need larger grid sizes, include a wheel graph and a cycle graph, a tree and a matching, or a pair of graphs both of which have maximum degree two. However, pairs of planar graphs and a matching, or of a tree and a path exist, that have no simultaneous geometric embedding. [4] [5] [6]

Testing whether two graphs admit a simultaneous geometric embedding is NP-hard. [1] [7] More precisely, it is complete for the existential theory of the reals. The proof of this result also implies that for some pairs of graphs that have simultaneous geometric embeddings, the smallest grid on which they can be drawn has doubly exponential size. [8] [2] When a simultaneous geometric embedding exists, it automatically is also a simultaneous embedding with fixed edges. [1]

Fixed edges

In simultaneous embedding with fixed edges, curves or bends are allowed in the edges, but any edge present in both graphs must be represented by the same curve in both drawings. [1] The classification of different types of input as always having an embedding or as sometimes not being possible depends not only on the two types of graphs to be drawn, but also on the structure of their intersection. For instance, it is always possible to find such an embedding when both of the two given graphs are outerplanar graphs and their intersection is a linear forest, with at most one bend per edge and with vertex coordinates and bend points all belonging to a grid of polynomial area. However, there exist other pairs of outerplanar graphs with more complex intersections that have no such embedding. It is also possible to find a simultaneous embedding with fixed edges for any pair of a planar graph and a tree. [9] [10] [11]

Unsolved problem in mathematics:

Can a simultaneous embedding with fixed edges for two given graphs be found in polynomial time?

(more unsolved problems in mathematics)

It is an open question whether the existence of a simultaneous embedding with fixed edges for two given graphs can be tested in polynomial time. However, for three or more graphs, the problem is NP-complete. When simultaneous embeddings with fixed edges do exist, they can be found in polynomial time for pairs of outerplanar graphs, and for Biconnected graphs, i.e. pairs of graphs whose intersection is biconnected. [1] [12] [13] [14]

Unrestricted

Any two planar graphs can have a simultaneous embedding. This may be done in a grid of polynomial area, with at most two bends per edge. Any two subhamiltonian graphs have a simultaneous embedding with at most one bend per edge. [1] [10] [15]

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.

Graph drawing

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.

Outerplanar graph

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.

Book embedding 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.

Planarity is a puzzle computer game by John Tantalo, based on a concept by Mary Radcliffe at Western Michigan University. The name comes from the concept of planar graphs in graph theory; these are graphs that can be embedded in the Euclidean plane so that no edges intersect. By Fáry's theorem, if a graph is planar, it can be drawn without crossings so that all of its edges are straight line segments. In the planarity game, the player is presented with a circular layout of a planar graph, with all the vertices placed on a single circle and with many crossings. The goal for the player is to eliminate all of the crossings and construct a straight-line embedding of the graph by moving the vertices one by one into better positions.

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.

Matchstick graph

In geometric graph theory, a branch of mathematics, a matchstick graph is a graph that can be drawn in the plane in such a way that its edges are line segments with length one that do not cross each other. That is, it is a graph that has an embedding which is simultaneously a unit distance graph and a plane graph. For this reason, matchstick graphs have also been called planar unit-distance graphs. Informally, matchstick graphs can be made by placing noncrossing matchsticks on a flat surface, hence the name.

Angular resolution (graph drawing)

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.

1-planar graph

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.

Circular layout

In graph drawing, a circular layout is a style of drawing that places the vertices of a graph on a circle, often evenly spaced so that they form the vertices of a regular polygon.

Arc diagram Type of graph drawing

An arc diagram is a style of graph drawing, in which the vertices of a graph are placed along a line in the Euclidean plane, with edges being drawn as semicircles in one or both of the two halfplanes bounded by the line, or as smooth curves formed by sequences of semicircles. In some cases, line segments of the line itself are also allowed as edges, as long as they connect only vertices that are consecutive along the line. Variations of this drawing style in which the semicircles are replaced by convex curves of some other type are also commonly called arc diagrams.

In graph drawing and geometric graph theory, a Tutte embedding or barycentric embedding of a simple 3-vertex-connected planar graph is a crossing-free straight-line embedding with the properties that the outer face is a convex polygon and that each interior vertex is at the average of its neighbors' positions. If the outer polygon is fixed, this condition on the interior vertices determines their position uniquely as the solution to a system of linear equations. Solving the equations geometrically produces a planar embedding. Tutte's spring theorem, proven by W. T. Tutte (1963), states that this unique solution is always crossing-free, and more strongly that every face of the resulting planar embedding is convex. It is called the spring theorem because such an embedding can be found as the equilibrium position for a system of springs representing the edges of the graph.

Upward planar drawing

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.

Dominance drawing

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 graph theory, the thickness of a graph G is the minimum number of planar graphs into which the edges of G can be partitioned. That is, if there exists a collection of k planar graphs, all having the same set of vertices, such that the union of these planar graphs is G, then the thickness of G is at most k. In other words, the thickness of a graph is the minimum number of planar subgraphs whose union equals to graph G.

In graph drawing, planarization is a method of extending 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, the area used by a drawing is a commonly used way of measuring its quality.

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.

Map graph

In graph theory, a branch of mathematics, a map graph is an undirected graph formed as the intersection graph of finitely many simply connected and internally disjoint regions of the Euclidean plane. The map graphs include the planar graphs, but are more general. Any number of regions can meet at a common corner, and when they do the map graph will contain a clique connecting the corresponding vertices, unlike planar graphs in which the largest cliques have only four vertices. Another example of a map graph is the king's graph, a map graph of the squares of the chessboard connecting pairs of squares between which the chess king can move.

References

  1. 1 2 3 4 5 6 7 8 9 10 11 12 Bläsius, Thomas; Kobourov, Stephen G.; Rutter, Ignaz (2013), "Simultaneous embedding of planar graphs", in Tamassia, Roberto (ed.), Handbook of Graph Drawing and Visualization, CRC Press, pp. 349–383, ISBN   9781420010268
  2. 1 2 Duncan, Christian; Eppstein, David; Kobourov, Stephen G. (2004), "The geometric thickness of low degree graphs", Proc. 20th ACM Symposium on Computational Geometry , ACM, pp. 340–346, arXiv: cs.CG/0312056 , doi:10.1145/997817.997868, S2CID   7595249 .
  3. ↑ Bläsius, Kobourov & Rutter (2013), Theorem 11.1.
  4. ↑ Bläsius, Kobourov & Rutter (2013), Figure 11.2.
  5. ↑ Brass, Peter; Cenek, Eowyn; Duncan, Christian A.; Efrat, Alon; Erten, Cesim; Ismailescu, Dan P.; Kobourov, Stephen G.; Lubiw, Anna; Mitchell, Joseph S. B. (2007), "On simultaneous planar graph embeddings", Computational Geometry Theory & Applications, 36 (2): 117–130, doi: 10.1016/j.comgeo.2006.05.006 , MR   2278011 .
  6. ↑ Cabello, Sergio; van Kreveld, Marc; Liotta, Giuseppe; Meijer, Henk; Speckmann, Bettina; Verbeek, Kevin (2011), "Geometric simultaneous embeddings of a graph and a matching", Journal of Graph Algorithms and Applications , 15 (1): 79–96, CiteSeerX   10.1.1.487.4749 , doi:10.7155/jgaa.00218, MR   2776002 .
  7. ↑ Estrella-Balderrama, Alejandro; Gassner, Elisabeth; Jünger, Michael; Percan, Merijam; Schaefer, Marcus; Schulz, Michael (2008), "Simultaneous geometric graph embeddings", Graph Drawing: 15th International Symposium, GD 2007, Sydney, Australia, September 24–26, 2007, Revised Papers, Lecture Notes in Computer Science, 4875, Berlin: Springer, pp. 280–290, doi: 10.1007/978-3-540-77537-9_28 , MR   2427826 .
  8. ↑ Cardinal, Jean; Kusters, Vincent (2015), "The complexity of simultaneous geometric graph embedding", Journal of Graph Algorithms and Applications, 19 (1): 259–272, doi: 10.7155/jgaa.00356 , MR   3344782, S2CID   12662906 .
  9. ↑ Bläsius, Kobourov & Rutter (2013), Figure 11.5.
  10. 1 2 Di Giacomo, Emilio; Liotta, Giuseppe (2007), "Simultaneous embedding of outerplanar graphs, paths, and cycles", International Journal of Computational Geometry & Applications, 17 (2): 139–160, doi:10.1142/S0218195907002276, MR   2309902 .
  11. ↑ Frati, Fabrizio (2007), "Embedding graphs simultaneously with fixed edges", Graph Drawing: 14th International Symposium, GD 2006, Karlsruhe, Germany, September 18–20, 2006, Revised Papers, Lecture Notes in Computer Science, 4372, Berlin: Springer, pp. 108–113, doi: 10.1007/978-3-540-70904-6_12 , MR   2393910 .
  12. ↑ Fowler, J. Joseph; Jünger, Michael; Kobourov, Stephen G.; Schulz, Michael (2011), "Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges", Computational Geometry Theory & Applications, 44 (8): 385–398, doi: 10.1016/j.comgeo.2011.02.002 , MR   2805957 .
  13. ↑ Gassner, Elisabeth; Jünger, Michael; Percan, Merijam; Schaefer, Marcus; Schulz, Michael (2006), "Simultaneous graph embeddings with fixed edges", Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers (PDF), Lecture Notes in Computer Science, 4271, Berlin: Springer, pp. 325–335, doi:10.1007/11917496_29, MR   2290741 .
  14. ↑ Haeupler, Bernhard; Jampani, Krishnam Raju; Lubiw, Anna (2013), "Testing simultaneous planarity when the common graph is 2-connected", Journal of Graph Algorithms and Applications , 17 (3): 147–171, arXiv: 1009.4517 , doi:10.7155/jgaa.00289, MR   3043207 .
  15. ↑ Di Giacomo, Emilio; Liotta, Giuseppe (2005), "A note on simultaneous embedding of planar graphs", 21st European Workshop on Computational Geometry (PDF), Eindhoven University of Technology .
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.