1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Scaffold for the Polyhedral Embedding of Cubic Graphs

Published Online: 16 Dec 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 21 Nov 2019
Accepted: 09 Oct 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

Let G be a cubic graph and Π be a polyhedral embedding of this graph. The extended graph, Ge, of Π is the graph whose set of vertices is V (Ge) = V (G) and whose set of edges E(Ge) is equal to E(G) ∪ 𝒮, where 𝒮 is constructed as follows: given two vertices t0 and t3 in V (Ge) we say [t0t3] ∈ 𝒮, if there is a 3-path, (t0t1t2t3) ∈ G that is a Π-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

MSC 2010

[1] 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. doi:/ 10.7151/dmgt.1816Open DOISearch in Google Scholar

[2] B. Mohar, Existence of polyhedral embeddings of graphs, Combinatorica 21 (2001) 395–401. doi: 10.1007/s004930100003Open DOISearch in Google Scholar

[3] B. Mohar, Uniqueness and minimality of large face-width embeddings of graphs, Combinatorica 15 (1995) 541–556. doi: 10.1007/BF01192526Open DOISearch in Google Scholar

[4] B. Mohar and N. Robertson, Flexibility of polyhedral embeddings of graphs in surfaces, J. Combin. Theory Ser. B 83 (2001) 38–57. doi: 10.1006/jctb.2001.2036Open DOISearch in Google Scholar

[5] B. Mohar and A. Vodopivec, On polyhedral embeddings of cubic graphs, Combin. Probab. Comput. 15 (2006) 877–893. doi: 10.1017/S0963548306007607Open DOISearch in Google Scholar

[6] G. Ringel, Map Color Theorem (Springer-Verlag, 1974). doi: 10.1007/978-3-642-65759-7Open DOISearch in Google Scholar

[7] N. Robertson and R. Vitray, Representativity of surface embeddings, in: Paths, Flows, and VLSI-Layout (Springer-Verlag, 1990) 293–328.Search in Google Scholar

[8] P. Seymour and R. Thomas, Uniqueness of highly representative surface embeddings, J. Graph Theory 23 (1966) 337–349. doi: 10.1002/(SICI)1097-0118(199612)23:4<337::AID-JGT2>3.0.CO;2-SOpen DOISearch in Google Scholar

[9] H. Whitney, 2-isomorphic graphs, Amer. J. Math. 55 (1933) 245–254. doi: 10.2307/2371127Open DOISearch in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo