Finding double Euler trails of planar graphs in linear time

Zhi Zhong Chen; Xin He; Chun Hsi Huang

Finding double Euler trails of planar graphs in linear time

Zhi Zhong Chen
, Xin He
, Chun Hsi Huang

Department of Computer Science and Engineering

Tokyo Denki University

Research output: Contribution to journal › Conference article › peer-review

3 Scopus citations

Abstract

This paper answers an open question in the design of complimentary metal-oxide semiconductor (CMOS) VLSI circuits. It asks whether a polynomial-time algorithm can decide if a given planar graph has a plane embedding E such that E has an Euler trail P = e₁e₂...e_m and its dual graph has an Euler trail P^* = e₁^*e₂^*...e_m^* where e_i^* is the dual edge of e_i for i = 1,2,...,m. This paper answers this question in the affirmative, by presenting a linear-time algorithm.

Original language	English
Pages (from-to)	319-329
Number of pages	11
Journal	Annual Symposium on Foundations of Computer Science - Proceedings
State	Published - 1999
Event	Proceedings of the 1999 IEEE 40th Annual Conference on Foundations of Computer Science - New York, NY, USA Duration: Oct 17 1999 → Oct 19 1999

Cite this

@article{4d1051107e0841ccb6ee6aafe8dbd937,

title = "Finding double Euler trails of planar graphs in linear time",

abstract = "This paper answers an open question in the design of complimentary metal-oxide semiconductor (CMOS) VLSI circuits. It asks whether a polynomial-time algorithm can decide if a given planar graph has a plane embedding E such that E has an Euler trail P = e1e2...em and its dual graph has an Euler trail P* = e1*e2*...em* where ei* is the dual edge of ei for i = 1,2,...,m. This paper answers this question in the affirmative, by presenting a linear-time algorithm.",

author = "Chen, \{Zhi Zhong\} and Xin He and Huang, \{Chun Hsi\}",

year = "1999",

language = "English",

pages = "319--329",

journal = "Annual Symposium on Foundations of Computer Science - Proceedings",

issn = "0272-5428",

publisher = "IEEE Computer Society",

note = "Proceedings of the 1999 IEEE 40th Annual Conference on Foundations of Computer Science ; Conference date: 17-10-1999 Through 19-10-1999",

}

TY - JOUR

T1 - Finding double Euler trails of planar graphs in linear time

AU - Chen, Zhi Zhong

AU - He, Xin

AU - Huang, Chun Hsi

PY - 1999

Y1 - 1999

N2 - This paper answers an open question in the design of complimentary metal-oxide semiconductor (CMOS) VLSI circuits. It asks whether a polynomial-time algorithm can decide if a given planar graph has a plane embedding E such that E has an Euler trail P = e1e2...em and its dual graph has an Euler trail P* = e1*e2*...em* where ei* is the dual edge of ei for i = 1,2,...,m. This paper answers this question in the affirmative, by presenting a linear-time algorithm.

AB - This paper answers an open question in the design of complimentary metal-oxide semiconductor (CMOS) VLSI circuits. It asks whether a polynomial-time algorithm can decide if a given planar graph has a plane embedding E such that E has an Euler trail P = e1e2...em and its dual graph has an Euler trail P* = e1*e2*...em* where ei* is the dual edge of ei for i = 1,2,...,m. This paper answers this question in the affirmative, by presenting a linear-time algorithm.

UR - https://www.scopus.com/pages/publications/0033316652

M3 - Conference article

AN - SCOPUS:0033316652

SN - 0272-5428

SP - 319

EP - 329

JO - Annual Symposium on Foundations of Computer Science - Proceedings

JF - Annual Symposium on Foundations of Computer Science - Proceedings

T2 - Proceedings of the 1999 IEEE 40th Annual Conference on Foundations of Computer Science

Y2 - 17 October 1999 through 19 October 1999

ER -

Finding double Euler trails of planar graphs in linear time

Abstract

Other files and links

Fingerprint

Cite this