A Note on Dual Trail Partition of a Plane Graph

Shuichi UENO; Katsufumi TSUJI; Yoji KAJITANI

Copy

Shuichi UENO, Katsufumi TSUJI, Yoji KAJITANI, "A Note on Dual Trail Partition of a Plane Graph" in IEICE TRANSACTIONS on Fundamentals, vol. E74-A, no. 7, pp. 1915-1917, July 1991, doi: .
Abstract: Given a plane graph G, a trail of G is said to be dual if it is also a trail in the geometric dual of G. We show that the problem of partitioning the edges of G into the minimum number of dual trails is NP-hard.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e74-a_7_1915/_p

Copy

@ARTICLE{e74-a_7_1915,
author={Shuichi UENO, Katsufumi TSUJI, Yoji KAJITANI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Note on Dual Trail Partition of a Plane Graph},
year={1991},
volume={E74-A},
number={7},
pages={1915-1917},
abstract={Given a plane graph G, a trail of G is said to be dual if it is also a trail in the geometric dual of G. We show that the problem of partitioning the edges of G into the minimum number of dual trails is NP-hard.},
keywords={},
doi={},
ISSN={},
month={July},}

Copy

TY - JOUR
TI - A Note on Dual Trail Partition of a Plane Graph
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1915
EP - 1917
AU - Shuichi UENO
AU - Katsufumi TSUJI
AU - Yoji KAJITANI
PY - 1991
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E74-A
IS - 7
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - July 1991
AB - Given a plane graph G, a trail of G is said to be dual if it is also a trail in the geometric dual of G. We show that the problem of partitioning the edges of G into the minimum number of dual trails is NP-hard.
ER -