A Characterization Theorem for Nonmaximal Partial-dual Planar Graphs and the Maximum Partial-dual Genus for a Planar Triangulated Graph
The partial duality GA of an embedded graph G can be seen as geometric duality over a partial edge set A of G.It is a generalization of the classic Poincaré duality G*.Unlike the classic Poincaré duality,the genus of GA is often not equal to the genus of G.Similar to the Huang-Liu's characterization theorem of non upper-embedability of graphs,we first prove a structure theorem for nonmaximal partial-dual planar graphs.Then,we determine the maximum partial-dual genus for a planar triangulated graph G,that is,if G is 3-cycle,the maximum partial-dual genus of G is 1;Otherwise the maximum partial-dual genus of G is equal to the number of vertices minus 1.
partial-dualthe maximal partial-dual planar graphplanar triangulated graphsthe maximum partial-dual genus
NETL
NSTL
万方数据
