Finding double euler trails of planar graphs in linear time

Zhi Zhong Chen; Xin He; Chun Hsi Huang

doi:10.1137/S0097539799354321

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 › Article › peer-review

2 Scopus citations

Abstract

This paper answers an open question in the design of complimentary metal-oxide semiconductor VLSI circuits. The question asks whether a polynomial-time algorithm can decide if a given planar graph has a plane embedding ε such that ε 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)	1255-1285
Number of pages	31
Journal	SIAM Journal on Computing
Volume	31
Issue number	4
DOIs	https://doi.org/10.1137/S0097539799354321
State	Published - Mar 2002

Keywords

Dual graph
Euler trail
Planar graph

Access to Document

10.1137/S0097539799354321

Cite this

@article{6d807f13b47d461d8e3fa9f79ea4f570,

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 VLSI circuits. The question asks whether a polynomial-time algorithm can decide if a given planar graph has a plane embedding ε such that ε has an Euler trail P = e1e2 ... em and its dual graph has an Euler trail P* = e*1e*2 ... e*m, 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.",

keywords = "Dual graph, Euler trail, Planar graph",

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

year = "2002",

month = mar,

doi = "10.1137/S0097539799354321",

language = "English",

volume = "31",

pages = "1255--1285",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "4",

}

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 - 2002/3

Y1 - 2002/3

N2 - This paper answers an open question in the design of complimentary metal-oxide semiconductor VLSI circuits. The question asks whether a polynomial-time algorithm can decide if a given planar graph has a plane embedding ε such that ε has an Euler trail P = e1e2 ... em and its dual graph has an Euler trail P* = e*1e*2 ... e*m, 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 VLSI circuits. The question asks whether a polynomial-time algorithm can decide if a given planar graph has a plane embedding ε such that ε has an Euler trail P = e1e2 ... em and its dual graph has an Euler trail P* = e*1e*2 ... e*m, 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.

KW - Dual graph

KW - Euler trail

KW - Planar graph

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

U2 - 10.1137/S0097539799354321

DO - 10.1137/S0097539799354321

M3 - Article

AN - SCOPUS:0036520592

SN - 0097-5397

VL - 31

SP - 1255

EP - 1285

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 4

ER -

Finding double euler trails of planar graphs in linear time

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this