Graph embedding algorithms

A topologi,cal 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 projectiue 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 ^9, we ask whether it is possible to ''251.This was published in the 1930s.However efficient algorithms to rec- ognize if a graph is planar appeared much later.For example, the popular linear time planarity-testing algorithm by J. Hopcroft and R. Tarjan [19] was published only in 7974.The ori,entable (non-ori,entable) genus of a graph is the smallest orientable (non-orientable) genus of a surface in which the graph can be embedded.In general, the problem of finding the genus of a graph was proved to be l/P-complete by C. Thomassen [36].Recently, Kuratowski's characterization of planar graphs v/as generalized for non-orientable surfaces by D. Archdeacon and J.P. Huneke [2] and for orientable surfaces by R.Bodendiek and K. Wagner [3].In a series of papers on graph minors, N. Robertson and P. Seymour [35] generalized Kuratowski's result for an arbitrary surface.This implies that for a given surface the ques- tion of whether a graph is embeddable into the surface can be answered in polynomial time.Moreover, B. Mohar [29] claimed to develop a series of linear time algorithms to answer the question.Unfortunately, these linear time algorithms appear to be infeasible, and are more of theoretical interest than practical.The de- scriptions of [28], [21] and [29] are missing many of the details necessary for an implementation of them.It is not clear if the approach is correct and covers all the cases providing a linear time algorithm.However, as it is mentioned in [41], the description of 128] gives some insights into the problem.The only known efficient implemented algorithm is the O(n') projective planarity-checking algorithm by W. Myrvold and J. Roth [30].This thesis is focussed on devising linear time practical algorithms to determine if there exists an embedding of a graph in the projective plane and/or torus.These are the topological surfaces closest to the plane.Early algorithms for these surfaces described in [12] and [32] are known to be wrong (personal communication by W. Myrvold).Many known algorithms for the projective plane and torus (eg.[30], [28] and [21]) begin with a Kuratowski subgraph Ks or K,s in a graph, and try to extend an embedding of K5 or Ks,s to an embedding of the whole graph on the corresponding surface.For a graph G containing a K5-subdivision, this thesis presents new algorithms to reduce the projective planarity or toroidality testing of G to a constant number of planarity checks or to a K,s-subdivision in G.For a graph G containing a K3,3-subdivision, the thesis provides a new detailed algorithm to tell if G is projective planar.In summary, we have devised a ne'vr/ Iinear time algorithm to detect a projective planar graph and a linear time algorithm that either determines the toroidality of a graph or returns a K3,3-subdivision in it.Chapter 2 provides basic notation, definitions and results related to the prob- lem and algorithms.Chapter 3 describes the main ideas of the Hopcroft-Tarjan planarity algorithm.The ideas and concepts of the planarity algorithm are used in different forms for other algorithms in the thesis.Necessary conditions for a 2-cell embedding of a graph on the projective plane and torus are given in Chapter 4. Section 4.3 presents methods for transforming a planar embed- ding into a2-cell embedding on the projective plane and torus.The methods are another main contribution of the thesis.They are used in the software GroupsJGraphs [2a].In Chapter 5, we describe known implemented general algorithms for the pro- jective plane and torus from [30] and [31].These algorithms help us to better understand surfaces with respect to the problem and its practical solution.The projective planarity checking algorithm of W. Myrvold and J. Roth has O(n2) time complexity, whereas the toroidality checking algorithm is exponential in the worst case.We have completely characterized projective planar and toroidal embeddings of certain kinds of graphs containing a K5-subdivision and developed linear time algorithms to tell if the graphs are projective planar or toroidal.Structural results for graphs containing a subdivision of K5 are presented in Chapter 6.Given a non-planar graph G with a subdivision of Ks as a subgraph, we can either transform the K5-subdivision into a Ks,g-subdivision in G, or else we obtain a partition of the vertices of G\/(s into equivalence classes.As a result, '/e can reduce a projective planarity or toroidality algorithm to a small constant number of planarity checks as in [19], or to a graph G containing a Ks,s-subdivision.The corresponding new algorithms are described in Section 7.1 for the projective plane and in Chapter 9 for the torus.Our new algorithms are reasonable to implement.This approach significantly simplifies algorithms presented in [21], [28] and [30].We then need to consider only the embeddings on the given surface of a K3,3-subdivision, which are much less numerous and more symmetric than those of K5.Also our new linear time algorithm of Chapter 9 can be used to restrict the exponential algorithm of [31] to graphs containing a K3,3-subdivision.A description of our new linear time projective planarity algorithm is presented in Chapters 7 and 8.This algorithm is more efficient than the O(n2) time algorithm of [30] described in Section 5.1.Chapter 7 describes structural results and all possible cases to complete a Ks,s-subdivision to an embedding of a graph G in the projective plane.We consider a spanning subdivision of.K3p in the graph.A case of a non-spanning Ks,s-subdivision in G can be treated recursively by using the recursion ideas of the Hopcroft-Tarjan planarity algorithm.Recent results of [11] suggest an efficient method to compute the orientable genus for a graph embedded in the projective plane.Our projective planarity algorithm can be used as a preliminary step to use the approach of [11].A graph embedding can be used to design a VLSI layout.Given a VLSI to design, we can represent its elements and wire connections by vertices and edges of a graph.Since connections between elements should not cross, v/e are interested in a drawing of the graph without edge crossing.This provides a practical motivation to obtain a graph embedding with particular properties.Chapter 2 Graphs and Surfaces: Basic Notation and ResultsBasic graph-theoretic terminology in this thesis follows Bondy and Murty [4] and Diestel [8].A graph G : (V, E) is undi,rected 1f. the edges of G are un- ordered pairs of vertices and G is si,mple if there are no multiple edges or loops.A graph G : (V, E) is 2-connected if for any two vertices)'tLiu e V, there are two internally disjoint paths in G with endpoints z and a.In other words, any two vertices u,u e V are on a cycle in G.In this thesis we consider the graph embedding problem for 2-connected, undirected, simple graphs.For graphs that are not 2-connected we can decide on their embedding in the plane, projective plane or torus by considering their maximal 2-connected subgraphs.Chapter 2 describes the polygon representation of the surfaces, defines an embedding of a graph and related things.Finally, the chapter describes basic results related to the graph embedding algorithms. 2.L Basic Notation and DefinitionsThe description of topological closed surfaces is taken from [13].The only topologically distinct (i.e.non-homeomorphic) types of.closed ori,entable sur- faces arc the sphere, the torus, and, in general, the generalized torus with p holes or the sphere with p handles (p:1,2,3,...).For closed non-ortentable surfaces, the only topologically distinct types are given by the sphere with q cross-caps (q : L,2,3,.. .).According to [13], any closed surface ^9 can be constructed from a curvilinear polygon homeomorphic to a circular disk by identifying sides in pairs.Each side from a pair is denoted by the same indexed symbol and is oriented on the polygon boundary.We use the superscript " * " to denote a clockwise orientation of a side, like a+, and the superscript " -" to denote a counter- clockwise orientation of a side, like -, on the polygon boundary.Also it can be proved that any surface ^9 can be decomposed into such a polygon.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.