Article in volume
Authors:
Title:
Scaffold for the polyhedral embedding of cubic graphs
PDFSource:
Discussiones Mathematicae Graph Theory 43(2) (2023) 351-384
Received: 2019-11-21 , Revised: 2020-10-08 , Accepted: 2020-10-09 , Available online: 2020-11-30 , https://doi.org/10.7151/dmgt.2379
Abstract:
Let $G$ be a cubic graph and $\Pi$ be a polyhedral embedding of this graph.
The extended graph, $G^{e},$ of $\Pi$ is the graph whose set of
vertices is $V(G^{e})=V(G)$ and whose set of edges $E(G^{e})$ is equal to
$E(G) \cup \mathcal{S}$, where $\mathcal{S}$ is constructed as follows: given
two vertices $t_0$ and $t_3$ in $V(G^{e})$ we say $[t_0 t_3] \in \mathcal{S},$
if there is a $3$-path, $(t_0 t_1 t_2 t_3) \in G$ that is a $\Pi$-facial
subwalk of the embedding. We prove that there is a one to one correspondence
between the set of possible extended graphs of $G$ and polyhedral embeddings
of $G$.
Keywords:
cubic graph, polyhedral embedding
References:
- J.L. Arocha, J. Bracho, N. García-Colín and I. Hubard, Reconstructing surface triangulations by their intersection matrices, Discuss. Math. Graph Theory 35 (2015) 483–491.
https://doi.org//10.7151/dmgt.1816 - B. Mohar, Existence of polyhedral embeddings of graphs, Combinatorica 21 (2001) 395–401.
https://doi.org/10.1007/s004930100003 - B. Mohar, Uniqueness and minimality of large face-width embeddings of graphs, Combinatorica 15 (1995) 541–556.
https://doi.org/10.1007/BF01192526 - B. Mohar and N. Robertson, Flexibility of polyhedral embeddings of graphs in surfaces, J. Combin. Theory Ser. B 83 (2001) 38–57.
https://doi.org/10.1006/jctb.2001.2036 - B. Mohar and A. Vodopivec, On polyhedral embeddings of cubic graphs, Combin. Probab. Comput. 15 (2006) 877–893.
https://doi.org/10.1017/S0963548306007607 - G. Ringel, Map Color Theorem (Springer-Verlag, 1974).
https://doi.org/10.1007/978-3-642-65759-7 - N. Robertson and R. Vitray, Representativity of surface embeddings, in: aths, Flows, and VLSI-Layout, (Springer-Verlag 1990) 293–328.
- P. Seymour and R. Thomas, Uniqueness of highly representative surface embeddings, J. Graph Theory 23 (1966) 337–349.
https://doi.org/10.1002/(SICI)1097-0118(199612)23:4<337::AID-JGT2>3.0.CO;2-S - H. Whitney, $2$-isomorphic graphs, Amer. J. Math. 55 (1933) 245–254.
https://doi.org/10.2307/2371127
Close