Simultaneous embedding
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]
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
[edit]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
[edit]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.
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 Angelini, Geyer, Neuwirth and Kaufmann showed that a tree and a path exist, that have no simultaneous geometric embedding.[3][4]
Testing whether two graphs admit a simultaneous geometric embedding is NP-hard.[1][5] 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.[6] [2] When a simultaneous geometric embedding exists, it automatically is also a simultaneous embedding with fixed edges.[1]
Fixed edges
[edit]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.[7][8][9]
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][10][11][12]
Unrestricted
[edit]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][8][13]
References
[edit]- ^ a b c d e f g h i j k l 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
- ^ a b 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.
- ^ 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.
- ^ 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.
- ^ 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, vol. 4875, Berlin: Springer, pp. 280–290, doi:10.1007/978-3-540-77537-9_28, MR 2427826.
- ^ Cardinal, Jean; Kusters, Vincent (2015), "The complexity of simultaneous geometric graph embedding", Journal of Graph Algorithms and Applications, 19 (1): 259–272, arXiv:1302.7127, doi:10.7155/jgaa.00356, MR 3344782, S2CID 12662906.
- ^ Bläsius, Kobourov & Rutter (2013), Figure 11.5.
- ^ a b 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.
- ^ 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, vol. 4372, Berlin: Springer, pp. 108–113, doi:10.1007/978-3-540-70904-6_12, MR 2393910.
- ^ 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.
- ^ 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, vol. 4271, Berlin: Springer, pp. 325–335, doi:10.1007/11917496_29, MR 2290741.
- ^ 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.
- ^ 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.