zbMATH — the first resource for mathematics

Boolean approach to planar embeddings of a graph. (English) Zbl 0780.05017
Summary: The purpose of this paper, which is a sequel of our paper [ibid., New Ser. 4, No. 4, 316-326 (1988; Zbl 0671.05031)], is to show the following results.
(1) Both of the problems of testing the planarity of graphs and embedding a planar graph into the plane are equivalent to finding a spanning tree in another graph whose order and size are bounded by a linear function of the order and the size of the original graph, respectively.
(2) The number of topologically non-equivalent planar embeddings of a Hamiltonian planar graph \(G\) is \(\tau(G)=2^{c(H)-1}\), where \(c(H)\) is the number of components of the graph \(H\) which is related to \(G\).

05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI
[1] Hammer, P. L. and Rudeanu, S., Boolean Methods in Operations Research and Related Areas, Springer Verlag, Berlin, Heidelberg, New York, 1968. · Zbl 0155.28001
[2] Wu Wentzun, On the realigation of complexes in Euclidean space (I),Acta Math. Sinica (in Chinese),5 (1955), 505–552.
[3] Wu Wentzun, Planar embedding of linear graphs,Kexue Tongbao (in Chinese),2 (1974) 226–228.
[4] Tutte, W. T., Toward a theory of crossing numbers,J. Comb. Theory,B (1970), 45–53. · Zbl 0187.20803
[5] Liu Yanpei, Modulo 2 programming and planar embeddings,Acta Math. Appl. Sinica (in Chinese),1 (1978), 395–406.
[6] Liu Yanpei, On the linearity of testing planarity of graphs,Chin. Ann. Math.,7B (1986), 425–434. · Zbl 0633.05024
[7] Auslander, L, and Parter, S. V., On embedding graphs in the sphere,J. Math. and Mech.,10 (1961), 517–523. · Zbl 0101.16704
[8] Hopcroft, J. E. and Tarjan, R.E., Efficient planarity testing,J. ACM.,21 (1974), 549–568. · Zbl 0307.68025
[9] Liu Yanpei, Boolean Planarity Characterization of Graphs, RUTCOR Research Report RRR, 38-87, Rutgers University, 1987. Also inActa Math. Sinica, New Series,4 (1988), 316–329
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.