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.展开更多
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.
文摘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.
