Scaffold for the polyhedral embedding of cubic graphs

Publication date: 26 November 2019

Abstract: Let

G

be a cubic graph and

P i

be a polyhedral embedding of this graph. The extended graph,

G^{e},

of

P i

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) c u p m a t h c a l S

, where

m a t h c a l S

is constructed as follows: given two vertices

t_{0}

and

t_{3}

in

V (G^{e})

we say

[t_{0} t_{3}] i n m a t h c a l S,

if there is a

3

--path,

(t_{0} t_{1} t_{2} t_{3}) i n G

that is a

P i

-- 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

.

This page was built for publication: Scaffold for the polyhedral embedding of cubic graphs