The edge-face chromatic number Xef （G） of a plane graph G is the least number of colors assigned to the edges and faces such that every adjacent or incident pair of them receives different colors. In this article, t...The edge-face chromatic number Xef （G） of a plane graph G is the least number of colors assigned to the edges and faces such that every adjacent or incident pair of them receives different colors. In this article, the authors prove that every 2-connected plane graph G with △（G）≥｜G｜ - 2≥9 has Xef（G） = △（G）.展开更多
Wang Wei-fan[1] proved that the edge-face chromatic number of a 2-connected 1-tree with the maximum degree is not less than 6 is its maximum degree, and he conjectured that it is true when the maximum degree is 5. Thi...Wang Wei-fan[1] proved that the edge-face chromatic number of a 2-connected 1-tree with the maximum degree is not less than 6 is its maximum degree, and he conjectured that it is true when the maximum degree is 5. This paper proves the conjecture.展开更多
Abstract Let G=(V,E,F)be a connected loopless plane graph,with vertex set V,edge set E,and face set F.For any adjacent faces e_(1) and e_(2),if they are incident to the same face and appear consecutively on the edge o...Abstract Let G=(V,E,F)be a connected loopless plane graph,with vertex set V,edge set E,and face set F.For any adjacent faces e_(1) and e_(2),if they are incident to the same face and appear consecutively on the edge of that face,then it is said that e1 and e_(2) are facially adjacent.A plane graph G is called weakly edge-face k-colorable indicating that there is a mappingπ:E∪F→{1,2,…,k}such that any two incident edges and faces,adjacent faces,and facially adjacent edges receive distinct colors.The weakly edge-face chromatic number of G,denoted by-χ_(ef)(G),is defined to be the smallest integer k such that G has a weakly edge-face k-coloring.In 2016,Fabrici conjectured that every connected,loopless,and bridgeless plane graph was weakly edge-face 5-colorable.In this paper,a sufficient condition is provided for the foregoing conjecture to prove that Halin graphs are weakly edge-face 5-colorable in which the upper bound 5 is the best possible.展开更多
Definition 1. Assume that G（V, E, F）is a 3-connected plane graph. Remove all edges on the boundary of a face f<sub>0</sub> whose degree of all vertices of $ V（f-0）$ is 3 such that G becomes a tree T wh...Definition 1. Assume that G（V, E, F）is a 3-connected plane graph. Remove all edges on the boundary of a face f<sub>0</sub> whose degree of all vertices of $ V（f-0）$ is 3 such that G becomes a tree T whose degree of all vertices except those of V（f<sub>0</sub>） is at least 3. Then G is called a Halin-graph, f<sub>0</sub>展开更多
The Point-In-Polyhedron problem is to check whether a point is inside or outside of a given polyhedron.When a degenerate case is detected,the traditional ray-crossing algorithms avoid the case by selecting a different...The Point-In-Polyhedron problem is to check whether a point is inside or outside of a given polyhedron.When a degenerate case is detected,the traditional ray-crossing algorithms avoid the case by selecting a different ray or erase the case by perturbing input data.This paper introduces a Threshold-Based Ray-Crossing (TBRC) algorithm for solving the Point-In-Polyhedron problem.The TBRC algorithm copes directly with degenerate cases by checking whether to count the face intersecting with the ray.It is worth mentioning that the TBRC algorithm can handle all degeneracies without extra computation and storage.Moreover,we analyze the basic algorithm and examine how to accelerate it.The experimental results show that TBRC algorithm is highly efficient and robust for the Point-In-Polyhedron problem,compared to a classical tetrahedron-based algorithm without pre-processing.展开更多
基金This research is supported by NNSF of China(40301037, 10471131)
文摘The edge-face chromatic number Xef （G） of a plane graph G is the least number of colors assigned to the edges and faces such that every adjacent or incident pair of them receives different colors. In this article, the authors prove that every 2-connected plane graph G with △（G）≥｜G｜ - 2≥9 has Xef（G） = △（G）.
文摘Wang Wei-fan[1] proved that the edge-face chromatic number of a 2-connected 1-tree with the maximum degree is not less than 6 is its maximum degree, and he conjectured that it is true when the maximum degree is 5. This paper proves the conjecture.
文摘Abstract Let G=(V,E,F)be a connected loopless plane graph,with vertex set V,edge set E,and face set F.For any adjacent faces e_(1) and e_(2),if they are incident to the same face and appear consecutively on the edge of that face,then it is said that e1 and e_(2) are facially adjacent.A plane graph G is called weakly edge-face k-colorable indicating that there is a mappingπ:E∪F→{1,2,…,k}such that any two incident edges and faces,adjacent faces,and facially adjacent edges receive distinct colors.The weakly edge-face chromatic number of G,denoted by-χ_(ef)(G),is defined to be the smallest integer k such that G has a weakly edge-face k-coloring.In 2016,Fabrici conjectured that every connected,loopless,and bridgeless plane graph was weakly edge-face 5-colorable.In this paper,a sufficient condition is provided for the foregoing conjecture to prove that Halin graphs are weakly edge-face 5-colorable in which the upper bound 5 is the best possible.
文摘Definition 1. Assume that G（V, E, F）is a 3-connected plane graph. Remove all edges on the boundary of a face f<sub>0</sub> whose degree of all vertices of $ V（f-0）$ is 3 such that G becomes a tree T whose degree of all vertices except those of V（f<sub>0</sub>） is at least 3. Then G is called a Halin-graph, f<sub>0</sub>
基金the Joint Foundation of Guangdong Province and CAS (No.2009B091300149)
文摘The Point-In-Polyhedron problem is to check whether a point is inside or outside of a given polyhedron.When a degenerate case is detected,the traditional ray-crossing algorithms avoid the case by selecting a different ray or erase the case by perturbing input data.This paper introduces a Threshold-Based Ray-Crossing (TBRC) algorithm for solving the Point-In-Polyhedron problem.The TBRC algorithm copes directly with degenerate cases by checking whether to count the face intersecting with the ray.It is worth mentioning that the TBRC algorithm can handle all degeneracies without extra computation and storage.Moreover,we analyze the basic algorithm and examine how to accelerate it.The experimental results show that TBRC algorithm is highly efficient and robust for the Point-In-Polyhedron problem,compared to a classical tetrahedron-based algorithm without pre-processing.
