TY - GEN
T1 - On Characterization of Petrie Partitionable Plane Graphs
AU - He, Xin
AU - Zhang, Huaming
N1 - Publisher Copyright: © 2020, Springer Nature Switzerland AG.
PY - 2020
Y1 - 2020
N2 - Given a plane graph, a Petrie tour of G is a tour P of G that alternately turns left and right at each step. A Petrie tour partition of G is a collection of Petrie tours so that each edge of G is in exactly one tour. A Petrie tour is called a Petrie cycle if all its vertices are distinct. A Petrie cycle partition of G is a collection of Petrie cycles so that each vertex of G is in exactly one cycle. In this paper, we characterize 3-regular (4-regular, resp.) plane graphs with Petrie cycle (tour, resp.) partitions. Given a 4-regular plane graph, a 3-regularization of G is a 3-regular plane graph obtained from G by splitting every vertex into two degree-3 vertices. G is called Petrie partitionable if it has a 3-regularization that has a Petrie cycle partition. In this paper, we present an elegant characterization of Petrie partitionable graphs. The general version of this problem is motivated by a data compression method, tristrip, used in computer graphics.
AB - Given a plane graph, a Petrie tour of G is a tour P of G that alternately turns left and right at each step. A Petrie tour partition of G is a collection of Petrie tours so that each edge of G is in exactly one tour. A Petrie tour is called a Petrie cycle if all its vertices are distinct. A Petrie cycle partition of G is a collection of Petrie cycles so that each vertex of G is in exactly one cycle. In this paper, we characterize 3-regular (4-regular, resp.) plane graphs with Petrie cycle (tour, resp.) partitions. Given a 4-regular plane graph, a 3-regularization of G is a 3-regular plane graph obtained from G by splitting every vertex into two degree-3 vertices. G is called Petrie partitionable if it has a 3-regularization that has a Petrie cycle partition. In this paper, we present an elegant characterization of Petrie partitionable graphs. The general version of this problem is motivated by a data compression method, tristrip, used in computer graphics.
UR - https://www.scopus.com/pages/publications/85093868819
U2 - 10.1007/978-3-030-59267-7_27
DO - 10.1007/978-3-030-59267-7_27
M3 - Conference contribution
SN - 9783030592660
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 313
EP - 326
BT - Theory and Applications of Models of Computation - 16th International Conference, TAMC 2020, Proceedings
A2 - Chen, Jianer
A2 - Feng, Qilong
A2 - Xu, Jinhui
PB - Springer Science and Business Media Deutschland GmbH
T2 - 16th Annual Conference on Theory and Applications of Models of Computation, TAMC 2020
Y2 - 18 October 2020 through 20 October 2020
ER -