Partially Broken Orientations of Eulerian Plane Graphs
Partially Broken Orientations of Eulerian Plane Graphs
复制标题
DOI：
10.1007/s00373-020-02152-1
复制
发表时间：
2020-03
影响因子：
0.7
通讯作者：
Gen Kawatani;Yusuke Suzuki
中科院分区：
文献类型：
--
作者：
Gen Kawatani;Yusuke Suzuki
众所周知，每个欧拉平面图G都是2可着色的，并且允许一个方向，该方向是对G的每条边的方向分配，使得传入边和传出边交替出现在任何周围；我们说这样的顶点v具有替代性质，并且这样的方向是好的。在本文中，我们讨论了欧拉平面图的方向，使得某些指定的顶点不具有交替属性（而其他顶点具有该属性），并根据欧拉平面图的径向图给出了表征。此外，对于给定的在平面上正确绘制的图形，我们讨论它是否具有良好的方向。
It is well-known that every Eulerian plane graphGis face 2-colorable and admits an orientation which is an assignment of a direction to each edge ofGsuch that incoming edges and outgoing edges appear alternately around any; we say that such a vertexvhas thealternate property, and that such an orientation isgood. In this paper, we discuss orientations given to Eulerian plane graphs such that some specified vertices do not have the alternate property (while the others have the property), and give a characterization in terms of theradial graphof the Eulerian plane graph. Furthermore, for a given properly drawn graph on the plane, we discuss whether it has a good orientation or not.