Planarity Testing of Graphs on Base of a Spring Model

Hotz, Günter and Lohse, Steffen (2002) Planarity Testing of Graphs on Base of a Spring Model. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 471-472 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_51).

Full text not available from this repository.

Abstract

It is well known that planar embeddings of 3-connected graphs are uniquely determined up to isomorphy of the induced complex of nodes, edges and faces of the plane or the 2-sphere [1]. Moreover, each of the isomorphy classes of these embeddings contains a representative that has a convex polygon as outer border and has all edges embedded as straight lines. We fixate the outer polygon of such embeddings and regard each remaining edge $e$ as a spring, its resilience being $\vert e\vert^k$ ($\vert e\vert$ euclidean length of $e$, $k\!\in\!\bbbr, 1\!<\!k\!<\!\infty$). For 3-connected graphs, exactly one power-balanced embedding for each $k$ exists, and this embedding is planar if and only if the graph with the fixated border polygon has a planar embedding inside that very polygon. For $k\!=\!1$ or $k\!=\!\infty$, some faces may be collapsed; we call such embeddings quasi-planar [2]. It is possible to decide the planarity of any graph embedding in linear time [3]. The motivation for this result was to develop a planarity test that simultaneously with the decision process constructs a concrete planar embedding. This algorithm should work in three steps: 1. Choose any circle of the graph and embed it as a convex polygon in the plane or as an equator of the 2-sphere. 2. Fixate this circle and hang in the rest of the graph. Substitute each edge by a spring of a fixed norm $k$ and compute its power-balanced position. 3. Decide if the computed embedding can be decomposed into two planar flanks. The graph is planar if and only if this is possible. On the sphere, these flanks should be represented by the two hemispheres belonging to the fixated circle.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_51
Classifications:M Methods > M.400 Force-directed / Energy-based
G Algorithms and Complexity > G.770 Planarity Testing
G Algorithms and Complexity > G.560 Geometry
ID Code:446

Repository Staff Only: item control page

References

Hotz, G.: Einbettung von Streckenkomplexen in die Ebene. Math. Annalen 167, 214-223 (1966)

Becker, B., Hotz, G.: On the Optimal Layout Planar Graphs with Fixed Boundary. SIAM Journal on Computing 16(5), 946-972 (1987)

Becker- Groh, U., Hotz, G.: Ein Planaritätstest für planar-konvexe Grapheneinbettung mit lin. Komplexität. Beiträge zur Algebra u. Geom. 18, 191-200 (1984)

Hotz, G., Reichert, A.: Hierarchischer Entwurf komplexer Systeme. Chapter 8 in: Wegener, I. (Ed.): Highlights aus der Informatik. Springer-Verlag (1996)

Osthof, H.-G.: Optimale Grapheneinbettung und ihre Anwendungen. Dissertation. Universität des Saarlandes (1990)

Fáry, I.: On Straight Line Representing of Planar Graphs, Acta Sci. Math.11, 229-233 (1948)

Schnyder, W.: Embedding Planar Graphs on the Grid. Proc. 1st ACM-SIAM Symp. on Discrete Alg., 138-148 (1990)

Mehlhorn, K., Näher, S., Seel, M., Uhrig, C.: The LEDA User Manual (Version 3.7) Max-Planck-Institut für Informatik, Saarbrücken (1999)

Lohse, S.: Ein Planaritätstest und Einbettungsverfahren für Graphen. Diplomarbeit. Fachbereich Informatik, Universität des Saarlandes (2001)