Graph embedding algorithms

XVT 8.3 8.4 8.5 I Torus Embeddings of Graphs Containing K5-Subdivisions 9.1 Embedding Ks-Subdivisions on the Torus and Planar Side Components 9.2 A Unique Non-Planar Side Component 9.3 Description of the Algorithm 10 Conclusions and F\rture'Work L79 180 187 194 t97xvil ''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 Groups€JGraphs [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.

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.