id: 00464618
dt: j
an: 00464618
au: Liu, Yanpei
ti: Boolean approach to planar embeddings of a graph.
so: Acta Math. Sin., New Ser. 5, No.1, 64-79 (1989).
py: 1989
pu: Science Press, Beijing; VSP, Utrecht
la: EN
cc: 
ut: planarity; spanning tree; planar embeddings; Hamiltonian planar graph;
    components
ci: Zbl 0671.05031
li: doi:10.1007/BF02107624
ab: 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
    $τ(G)=2\sp{c(H)-1}$, where $c(H)$ is the number of components of the
    graph $H$ which is related to $G$.
rv: