Graph ear decompositions and graph embeddings Conference Paper

abstract

• 1994, Springer Verlag. All rights reserved. Ear decomposition of a graph has been extensively studied in relation to graph connectivity. In this paper, a connection of ear decomposition to graph embeddings is exhibited. It is shown that constructing a maximumpaired ear decomposition of a graph and constructing a maximum-genus embedding of the graph are O (e log n)-time equivalent. This gives a polynomial time algorithm for constructing a maximum-paired ear decomposition.

authors

• Chen, Jianer

published proceedings

• Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

• Chen, J., & Kanchi, S. P.

complete list of authors

• Chen, J||Kanchi, SP

publication date

• January 1994

published in

• Lecture Notes in Artificial Intelligence  Journal

International Standard Book Number (ISBN) 13

• 9783540578994

start page

• 376

end page

• 387

volume

• 790 LNCS