|本期目录/Table of Contents|

[1]张维娟.平面及球面嵌入图α-定向的flip-距离[J].厦门大学学报(自然科学版),2019,58(02):282-287.[doi:10.6043/j.issn.0438-0479.201807034]
 ZHANG Weijuan.Flip-distance between α-orientations of graphs embedded on the plane and sphere[J].Journal of Xiamen University(Natural Science),2019,58(02):282-287.[doi:10.6043/j.issn.0438-0479.201807034]
点击复制

平面及球面嵌入图α-定向的flip-距离(PDF/HTML)
分享到:

《厦门大学学报(自然科学版)》[ISSN:0438-0479/CN:35-1070/N]

卷:
58卷
期数:
2019年02期
页码:
282-287
栏目:
研究论文
出版日期:
2019-03-27

文章信息/Info

Title:
Flip-distance between α-orientations of graphs embedded on the plane and sphere
文章编号:
0438-0479(2019)02-0282-06
作者:
张维娟12
1.厦门大学数学科学学院,福建 厦门 361005; 2.新疆师范大学数学科学学院,新疆 乌鲁木齐 830017
Author(s):
ZHANG Weijuan12
1.School of Mathematical Sciences,Xiamen University,Xiamen 361005,China; 2.School of Mathematical Sciences,Xinjiang Normal University,Urumqi 830017,China
关键词:
α-定向 flip-距离 平面嵌入图 球面嵌入图
Keywords:
α-orientation flip-distance plane graph sphere graph
分类号:
O 157.5
DOI:
10.6043/j.issn.0438-0479.201807034
文献标志码:
A
摘要:
为研究平面嵌入图的给定出度序列的定向问题,Felsner 引入了α-定向及flip变换,并进一步证明了一个平面嵌入图的所有α- 定向在flip变换下构成一个分配格. 本文中给出平面嵌入图的一个α-定向可由另一个α-定向通过一系列flip变换而得到的一个充分必要条件.与之平行,证明了球面嵌入图的任意两个α-定向均可通过一系列 flip 变换而相互得到. 最后,给出了所需最少flip变换的数目.
Abstract:
Felsner introduced a cycle reversal,namely the "flip" reversal,for α-orientations(i.e.,each vertex admits a prescribed out-degree)of a graph G embedded on the plane and further proved that the set of all the α-orientations of G carries a distributive lattice by flip reversals.In this paper,we give an explicit formula for the minimum number of flips needed to transform an α-orientation into another for graphs embedded on the plane and sphere,respectively.

参考文献/References:

[1] ROBBINS H E.A theorem or graphs,with an application to a problem of traffic control[J].Amer Math Monthly 1939,46(5):281-283.
[2] NASH-WILLIAMS C S J A.On orientation,connectivity and odd-vertex pairing in finite graphs[J].Canad J Math,1960,12:555-567.
[3] FRANK A,GYáRFáS A.How to orient the edges of a graph[J].Colloq Math Soc János Bolyai,1976,18:353-364.
[4] HAKIMI S L.On the degrees of the vertices of a directed graph[J].Journal of the Franklin Institute,1965,279(4):290-308.
[5] FELSNER S.Lattice structures from planar graphs[J].Electron J Combin,2004,11:R15.
[6] KENYON R,PROPP J,WILSON D B.Trees and matchings[J].Electron J Combin 2000,7(1):R25.
[7] LAM P C B,ZHANG H P.A distributive lattice on the set of perfect matchings of a plane bipartite graph[J].Order,2003,20:13-29.
[8] PROPP J.Lattice structure for orientations of graphs[EB/OL].[2018-06-01].http:∥arxiv.org/abs/math 0209005v1.
[9] FRAYSSEIX H D,MENDEZ P O D.On topological aspects of orientation[J].Discrete Math,2001,229:57-72.
[10] FRAYSSEIX H D,MENDEZ P O D,ROSENSTIEHL P.Bipolar orientations revisited[J].Discrete Appl Math,1995,56:157-179.
[11] DISSER Y,MATUSCHKE J.Degree-constrained orientations of embedded graphs[J].J Comb Optim,2016,31:758-773.
[12] FUSY E.Transversal structures on triangulations:a combinatorial study and straight-line drawings[J].Discrete Math,2009,309:1870-1894.
[13] KNAUER K B.Partial orders on orientations via cycle flips[D].Berlin:Technische Universit?t Berlin,2007:1-85.
[14] FELSNER S,ZICKFELD F.On the number of planar orientations with prescribed degrees[J].Electron J Combin,2008,15:R77.
[15] BONICHON N,FELSNER S,MOSBAH M.Convex drawings of 3-connected planar graphs[J].Algorithmica,2007,47:399-420.
[16] BARRERA-CRUZ C.Morphing planar triangulations[D].Ontario:The University of Waterloo,2014:1-128.
[17] CREED P J.Counting and sampling problems on eulerian graphs[D].Edinburgh:University of Edinburgh,2010:1-171.
[18] FUSY E,POULALHON D,SCHAEFFER G.Dissections and trees,with applications to optimal mesh encoding and to random sampling[C]∥SODA’05:Proceedings of the 16th annual ACM-SIAM Symposium on Discrete Algorithms.New York:ACM,2005:690-699.
[19] NAKAMOTO A,OTA K,TANUMA T.Three-cycle reversions in oriented planar triangulations[J].Yokohama Math J,1997,44:123-139.
[20] ZHANG F J,GUO X F,CHEN R S.Z-transformation graphs of perfect matchings of hexagonal systems[J].Discrete Math,1988, 72:405-415.
[21] Zhang H P,Zhang F J.Plane elementary bipartite graphs[J].Discrete Appl Math,2000,105:291-311.
[22] GON?ALVES D,KNAUER K B,LéVêQUE B.On the structure of Schnyder woods on orientable surfaces [EB/OL].[2018-06-01].http:∥arxiv.org/abs/ 1501.05475v2.
[23] HASSIN R.Maximum flow in(s,t)planar networks [J].Information Processing Letters,1981,13:107-107.[1] ROBBINS H E.A theorem or graphs,with an application to a problem of traffic control[J].Amer Math Monthly 1939,46(5):281-283.
[2] NASH-WILLIAMS C S J A.On orientation,connectivity and odd-vertex pairing in finite graphs[J].Canad J Math,1960,12:555-567.
[3] FRANK A,GYáRFáS A.How to orient the edges of a graph[J].Colloq Math Soc János Bolyai,1976,18:353-364.
[4] HAKIMI S L.On the degrees of the vertices of a directed graph[J].Journal of the Franklin Institute,1965,279(4):290-308.
[5] FELSNER S.Lattice structures from planar graphs[J].Electron J Combin,2004,11:R15.
[6] KENYON R,PROPP J,WILSON D B.Trees and matchings[J].Electron J Combin 2000,7(1):R25.
[7] LAM P C B,ZHANG H P.A distributive lattice on the set of perfect matchings of a plane bipartite graph[J].Order,2003,20:13-29.
[8] PROPP J.Lattice structure for orientations of graphs[EB/OL].[2018-06-01].http:∥arxiv.org/abs/math 0209005v1.
[9] FRAYSSEIX H D,MENDEZ P O D.On topological aspects of orientation[J].Discrete Math,2001,229:57-72.
[10] FRAYSSEIX H D,MENDEZ P O D,ROSENSTIEHL P.Bipolar orientations revisited[J].Discrete Appl Math,1995,56:157-179.
[11] DISSER Y,MATUSCHKE J.Degree-constrained orientations of embedded graphs[J].J Comb Optim,2016,31:758-773.
[12] FUSY E.Transversal structures on triangulations:a combinatorial study and straight-line drawings[J].Discrete Math,2009,309:1870-1894.
[13] KNAUER K B.Partial orders on orientations via cycle flips[D].Berlin:Technische Universit?t Berlin,2007:1-85.
[14] FELSNER S,ZICKFELD F.On the number of planar orientations with prescribed degrees[J].Electron J Combin,2008,15:R77.
[15] BONICHON N,FELSNER S,MOSBAH M.Convex drawings of 3-connected planar graphs[J].Algorithmica,2007,47:399-420.
[16] BARRERA-CRUZ C.Morphing planar triangulations[D].Ontario:The University of Waterloo,2014:1-128.
[17] CREED P J.Counting and sampling problems on eulerian graphs[D].Edinburgh:University of Edinburgh,2010:1-171.
[18] FUSY E,POULALHON D,SCHAEFFER G.Dissections and trees,with applications to optimal mesh encoding and to random sampling[C]∥SODA’05:Proceedings of the 16th annual ACM-SIAM Symposium on Discrete Algorithms.New York:ACM,2005:690-699.
[19] NAKAMOTO A,OTA K,TANUMA T.Three-cycle reversions in oriented planar triangulations[J].Yokohama Math J,1997,44:123-139.
[20] ZHANG F J,GUO X F,CHEN R S.Z-transformation graphs of perfect matchings of hexagonal systems[J].Discrete Math,1988, 72:405-415.
[21] Zhang H P,Zhang F J.Plane elementary bipartite graphs[J].Discrete Appl Math,2000,105:291-311.
[22] GON?ALVES D,KNAUER K B,LéVêQUE B.On the structure of Schnyder woods on orientable surfaces [EB/OL].[2018-06-01].http:∥arxiv.org/abs/ 1501.05475v2.
[23] HASSIN R.Maximum flow in(s,t)planar networks [J].Information Processing Letters,1981,13:107-107.

备注/Memo

备注/Memo:
收稿日期:2018-07-23 录用日期:2018-09-25
基金项目:国家自然科学基金(11471273,11561058)
Email:zhangweijuan828@163.com
更新日期/Last Update: 1900-01-01