Graph embedding algorithms
William Lawrence Kocay, Andrei Gagarin · 2003
A topological surface S can be obtained from the sphere by adding a number of handles and/or cross-caps. Any topological surface can be represented as a polygon whose sides are identified in pairs. The projective plane can be represented as a circular disk with opposite pairs of points on its boundary identified. The torus can be represented as a rectangle with opposite sides of its boundary identified. Given a graph G and a topological surface S , we ask whether it is possible to draw the graph on the surface without edge crossings. Such a drawing of G on the surface is called an embedding of G in S. It divides the surface into connected regions called faces. An embedding is 2-cell if each face is equivalent to an open disk. Efficient embedding algorithms for the plane are well-known. By Kuratowski's Theorem, a non-planar graph G contains a subdivision of K5 or K3,3 as a subgraph. The objective of this thesis is to devise efficient practical embedding algorithms for the projective plane and torus. The major contributions of the thesis are: (1) A new linear time algorithm to detect a projective planar graph; (2) Given a K 5-subdivision in G, a linear time algorithm to determine if G is toroidal or to provide a K 3,3-subdivision in G; (3) Simple methods to transform a planar embedding into a 2-cell projective planar or toroidal embedding. The known linear time algorithm for the projective plane in [28] appears to be infeasible and it is not clear if the approach is correct. The practical linear time projective planarity algorithm of the thesis improves the O(n2) time algorithm of [30]. The algorithm for the torus permits to reduce toroidality testing to a constant number of planarity checks or to a K3,3-subdivision in the graph. It runs in linear time and can be used to simplify algorithms presented in [21] and [31].